Alien Dictionary

Intuition

The sorted order between two neighboring words is decided by the first position where their characters differ: the earlier word's character must come before the later word's character in the alien alphabet. Each such comparison contributes exactly one directed edge between two letters. Collecting these edges builds a precedence graph over every letter that appears in the input. A topological order of that graph is precisely a valid alphabet, and Kahn's algorithm produces one while simultaneously exposing contradictions. If a letter never becomes free of its dependencies, the constraints contain a cycle and no ordering can exist. We also guard the special invalid case where a longer word precedes one of its own prefixes.

Algorithm walkthrough

1. 1Register every distinct letter across all words with an in-degree of zero so that isolated letters still appear in the result.
2. 2For each adjacent pair of words, scan until the first differing character, then add an edge from the earlier word's letter to the later word's letter and increment the target's in-degree.
3. 3If the words share a common prefix but the earlier word is longer (for example "abc" before "ab"), the input is invalid, so return an empty string immediately.
4. 4Seed a queue with every letter whose in-degree is zero, then repeatedly pop a letter, append it to the answer, and decrement its neighbors, enqueuing any that reach in-degree zero.
5. 5If the produced string contains every seen letter, return it; otherwise a cycle prevented a full ordering, so return an empty string.

Implementation

from collections import deque, defaultdict
from typing import List

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        adj = defaultdict(set)
        indegree = {c: 0 for word in words for c in word}

        for i in range(len(words) - 1):
            first, second = words[i], words[i + 1]
            min_len = min(len(first), len(second))
            if len(first) > len(second) and first[:min_len] == second[:min_len]:
                return ""
            for j in range(min_len):
                if first[j] != second[j]:
                    if second[j] not in adj[first[j]]:
                        adj[first[j]].add(second[j])
                        indegree[second[j]] += 1
                    break

        queue = deque([c for c in indegree if indegree[c] == 0])
        result = []
        while queue:
            c = queue.popleft()
            result.append(c)
            for nxt in adj[c]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        if len(result) < len(indegree):
            return ""
        return "".join(result)