forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathalien-dictionary.py
More file actions
executable file
·37 lines (33 loc) · 1.09 KB
/
alien-dictionary.py
File metadata and controls
executable file
·37 lines (33 loc) · 1.09 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
Topological Sort
"""
class Solution(object):
def alienOrder(self, words):
#return true if cycles are detected.
def dfs(c):
if c in path: return True
if c in visited: return False
path.add(c)
for nei in adj[c]:
if dfs(nei): return True
res.append(c)
path.remove(c)
visited.add(c)
return False
#build adjacency list
adj = {c: set() for word in words for c in word}
for i in xrange(len(words)-1):
w1, w2 = words[i], words[i+1]
minLen = min(len(w1), len(w2))
if w1[:minLen]==w2[:minLen] and len(w1)>len(w2): return ""
for j in xrange(minLen):
if w1[j]!=w2[j]:
adj[w1[j]].add(w2[j])
break
#topological sort
path = set() #path currently being reversed
visited = set() #done processing
res = []
for c in adj:
if dfs(c): return ""
return "".join(reversed(res))