## # 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: build pairs of ordering, then find cycles in the graph.

### # Code (Python)

Approach 1 (not verified on leetcode):

``````def derive_order(dictionary):

# build pairs of ordering
if not dictionary:
return ''
pairs = {}
for i in range(1, len(dictionary)):
prev_word, word = dictionary[i-1], dictionary[i]
letter_order = _derive_letter_order(prev_word, word)
if letter_order:
prev_letter, next_letter = letter_order
if prev_letter not in pairs:
pairs[prev_letter] = []
pairs[prev_letter].append(next_letter)

# build global ordering
ordering = []
visited = {}
IN_PROGRESS = 0
FINISHED = 1

# dfs to find cycles
def dfs(letter):
if letter in visited and visited[letter] == IN_PROGRESS:
return False
if letter not in visited:
visited[letter] = IN_PROGRESS
ordering.append(letter)
if letter in pairs:
for next_letter in pairs[letter]:
if not dfs(next_letter):
return False
visited[letter] = FINISHED
return True

if dfs(dictionary):
return ''.join(ordering)
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"
]
tests = [test1, test2, test3]