minglish_lesson solution

minglish_lesson.py

def answer(words):
    # first, we need to generate the graph
    vertices = []
    letters = list(set([val for sublist in [list(word) for word in words] for val in sublist]))
    
    for word in words:
        for letter in list(word):
            letters.append(letter)
    
    for i in range(len(words) - 1):
        word_a = words[i]
        word_b = words[i + 1]
        
        for j in range(min(len(word_a), len(word_b))):
            if word_a[j] != word_b[j]:
                letter_a = word_a[j]
                letter_b = word_b[j]
                
                vertices.append((letter_a, letter_b))
                
                break
    
    dfs = []
    marked = []
    pool = letters # the pool of letters. needed because I use pop()
    
    while len(pool) > 0:
        node = pool.pop()
        visit(node, vertices, dfs, marked)
    
    return ''.join(dfs)

def visit(node, vertices, dfs, marked):
    if node not in marked:
        marked.append(node)
        for vertex in vertices:
            if vertex[0] == node:
                visit(vertex[1], vertices, dfs, marked)
        
        dfs.insert(0, node)

print(answer(["z", "yx", "yz"])) # xzy
print(answer(["ba", "ab", "cb"])) # bac
print(answer(["y", "z", "xy"])) # yzx
print(answer(['c', 'cac', 'cb', 'bcc', 'ba'])) # cab
print(answer(['abc', 'bad', 'dba', 'cab'])) # a > b; b > d; d > c
print answer(['abc', 'abd', 'bda', 'cda']) # c > d; a > b; b > c