# Untitled

Sep 14th, 2021
1,065
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution:
2.     def alienOrder(self, words: List[str]) -> str:
3.         N_ALPHA = 26
4.         FREE, VISITED, LEFT = 0, 1, 2
5.         n = len(words)
6.
7.         def charCode(char: str) -> int:
8.             return ord(char) - ord('a')
9.         def codeChar(code: int) -> str:
10.             return chr(code + ord('a'))
11.
12.         def cmp2Words(w1: str, w2: str, graph: List[List[int]], used: List[bool]) -> bool:
13.             for i in range(min(len(w1), len(w2))):
14.                 if w1[i] != w2[i]:
15.                     graph[charCode(w1[i])].append(charCode(w2[i]))
16.                     return True
17.             return len(w1) <= len(w2)
18.
19.         def topSort(v: int, graph: List[List[int]], visited: List[bool], order: List[int]) -> bool:
20.             visited[v] = VISITED
21.             for u in graph[v]:
22.                 if visited[u] == VISITED:
23.                     return False
24.                 if visited[u] == LEFT:
25.                     continue
26.                 if not topSort(u, graph, visited, order):
27.                     return False
28.
29.             order.append(v)
30.             visited[v] = LEFT
31.             return True
32.
33.         used = [False]*N_ALPHA
34.         for word in words:
35.             for char in word:
36.                 used[charCode(char)] = True
37.
38.         graph = [[] for _ in range(N_ALPHA)]
39.         for i in range(1, n):
40.             if not cmp2Words(words[i-1], words[i], graph, used):
41.                 return ""
42.
43.         visited = [FREE]*N_ALPHA
44.         order = []
45.         for v in range(N_ALPHA):
46.             if not used[v] or visited[v]:
47.                 continue
48.             if not topSort(v, graph, visited, order):
49.                 return ""
50.         return ''.join(map(codeChar, reversed(order)))
RAW Paste Data