cyga

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