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