[LeetCode] 269. Alien Dictionary

 Problem : https://leetcode.com/problems/alien-dictionary/

Use topological sort to find order of letters.

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(list)
        indegree = defaultdict(int)
        
        for i in range(1, len(words)):
            for a, b in zip(words[i-1], words[i]):        
                if a != b:
                    graph[a].append(b)
                    indegree[b] += 1
                    break
            else:
                if len(words[i-1]) > len(words[i]):
                    return ''
        
        letters = set([l for w in words for l in w])
        queue = deque([l for l in letters if indegree[l] == 0])
                    
        result = []
        
        while queue:
            for _ in range(len(queue)):
                a = queue.popleft()
                result.append(a)
                
                for b in graph[a]:
                    indegree[b] -= 1
                    if indegree[b] == 0:
                        queue.append(b)
        
        # result is valid if all letters have be resolved.
        return ''.join(result) if len(result) == len(letters) else ""

Edited on 07/22/2021. Update for a shorter solution.