| 1 | class Solution: |
| 2 | def alienOrder(self, words: List[str]) -> str: |
| 3 | adj = {char: set() for word in words for char in word} |
| 4 | |
| 5 | for i in range(len(words) - 1): |
| 6 | w1, w2 = words[i], words[i + 1] |
| 7 | minLen = min(len(w1), len(w2)) |
| 8 | if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]: |
| 9 | return "" |
| 10 | for j in range(minLen): |
| 11 | if w1[j] != w2[j]: |
| 12 | print(w1[j], w2[j]) |
| 13 | adj[w1[j]].add(w2[j]) |
| 14 | break |
| 15 | |
| 16 | visited = {} # {char: bool} False visited, True current path |
| 17 | res = [] |
| 18 | |
| 19 | def dfs(char): |
| 20 | if char in visited: |
| 21 | return visited[char] |
| 22 | |
| 23 | visited[char] = True |
| 24 | |
| 25 | for neighChar in adj[char]: |
| 26 | if dfs(neighChar): |
| 27 | return True |
| 28 | |
| 29 | visited[char] = False |
| 30 | res.append(char) |
| 31 | |
| 32 | for char in adj: |
| 33 | if dfs(char): |
| 34 | return "" |
| 35 | |
| 36 | res.reverse() |
| 37 | return "".join(res) |