269. Alien Dictionary

We want to reconstruct a sorted list of words from a language with unknown order. We use pairwise to iterate through the words in the list, and build a graph that indicates the letters that must come before the others in the ordering.

Then we topologically sort — starting with valid nodes. We then keep adding words that are able to be enqueued in order.

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj = defaultdict(set)
        indegree = {c: 0 for word in words for c in word}
 
        for w1, w2 in pairwise(words):
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""  
            for c, d in zip(w1, w2):
                if c != d:
                    if d not in adj[c]:
                        adj[c].add(d)
                        indegree[d] += 1
                    break
 
        queue = deque([c for c in indegree if indegree[c] == 0])
        order = []
 
        while queue:
            c = queue.popleft()
            order.append(c)
            for nei in adj[c]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)
 
        return "".join(order) if len(order) == len(indegree) else ""