## # 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
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)):