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:
Given the following words in dictionary,
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
The correct order is: "wertf".
Example 2:
Given the following words in dictionary,
[
"z",
"x"
]
The correct order is: "zx".
Example 3:
Given the following words in dictionary,
[
"z",
"x",
"z"
]
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: Topological Sort
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
graph = dict()
pre = ''
for word in words:
same_prefix = True
for idx, char in enumerate(word):
if char not in graph:
graph[char] = set()
if same_prefix and idx < len(pre) and pre[idx] != char:
graph[pre[idx]].add(char)
same_prefix = False
if same_prefix and len(pre) > len(word):
return ''
pre = word
return ''.join(self.topological_order(graph))
def topological_order(self, graph):
order = []
cycle = []
visited = set()
visiting = set()
def dfs(node):
if cycle or node in visited:
return
if node in visiting:
cycle.append(1)
return
visiting.add(node)
for neighbor in graph[node]:
dfs(neighbor)
visiting.remove(node)
visited.add(node)
order.append(node)
for key in graph:
dfs(key)
if cycle:
return []
order.reverse()
return order