# 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

Example 2:

Input:
[
  "z",
  "x"
]

Output: "zx"

Example 3:

Input:
[
  "z",
  "x",
  "z"
] 

Output: "" 
Explanation: The order is invalid, so return "".

Note:

You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

# Solution

Approach 1: this is a topological sorting problem. After building the edges, use DFS to record visit order and find cycles.

# Code (Python)

Approach 1 (not verified on leetcode):

def derive_order(dictionary):
    
    # build edges
    edges = {}
    all_letters = set()
    for i in range(1, len(dictionary)):
        prev_word, word = dictionary[i-1], dictionary[i]
        print(prev_word, word)
        letter_order = _derive_letter_order(prev_word, word)
        print(letter_order)
        if not letter_order:
            continue
        prev_letter, next_letter = letter_order
        all_letters.add(prev_letter)
        all_letters.add(next_letter)
        if prev_letter not in edges:
            edges[prev_letter] = []
        edges[prev_letter].append(next_letter)
        print(edges)

    # topological sorting via DFS
    NOT_VISITED = -1
    IN_PROGRESS = 0
    FINISHED = 1

    ordering = []
    status = {letter: NOT_VISITED for letter in all_letters}

    # the dfs algorithm also finds cycles
    def dfs(letter):
        if status[letter] == FINISHED:
            return True
        if status[letter] == IN_PROGRESS:
            return False
        status[letter] = IN_PROGRESS
        if letter in edges:
            for neighbor in edges[letter]:
                if not dfs(neighbor):
                    return False
        status[letter] = FINISHED
        # append only after a visit is finished
        ordering.append(letter)
        return True
    
    if dfs(dictionary[0][0]):
        # result in reverse order
        return ''.join(ordering)[::-1]
    return ''

def _derive_letter_order(word1, word2):
    # assuming word1 != word2 and there's word2 isn't a prefix of word1
    for i in range(min(len(word1), len(word2))):
        if word1[i] != word2[i]:
            return [word1[i], word2[i]]
    return []

test1 = [
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
test2 = [
  "z",
  "x"
]
test3 = [
  "z",
  "x",
  "z"
] 
test4 = [
  "aa",
  "ac",
  "ba",
  "bc",
  "c"
]
tests = [test1, test2, test3, test4]
answers = ["wertf", "zx", "", "abc"]

for i in range(len(tests)):
    my_answer = derive_order(tests[i])
    print(tests[i], my_answer)
    assert my_answer == answers[i]

# Code (C++)

Approach 1:

Approach 2: