Simple Python solution, best runtime


  • 0
    from collections import deque
    
    class Solution(object):
        def alienOrder(self, words):
            chars = set(c for w in words for c in w)
            graph, indeg = {c:[] for c in chars}, {c:0 for c in chars}
            for pair in zip(words, words[1:]):
                for c1, c2 in zip(*pair):
                    if c1 != c2:
                        graph[c1] += c2,
                        indeg[c2] += 1
                        break
    
            queue = deque([char 
                           for char in indeg 
                           if not indeg[char]])
            ret = ""
            while queue:
                char = queue.popleft()
                ret += char
                for n in graph[char]:
                    indeg[n] -= 1
                    if not indeg[n]:
                        queue.append(n)
            return ret * (set(ret) == chars)
    
    # Runtime: 48ms

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.