Alien Dictionary

PracticeNeetCode ↗LeetCode ↗

A list of words is sorted according to the unknown alphabet rules of an alien language. Derive a valid ordering of that alphabet's letters from the word list. Return an empty string if no valid ordering exists.

Example

Key Pointers

• Only adjacent word pairs carry information — the first character where two consecutive words differ tells you one letter precedes another.
• If a later word is a strict prefix of an earlier, longer word (e.g. ["abc","ab"]), the ordering is invalid — that can never happen in a correctly sorted list.
• Turning the pairwise constraints into a directed graph reduces this to a topological sort; a cycle in that graph means no valid ordering exists.

Step-by-Step Analysis

1. Initialize an adjacency set and an in-degree of 0 for every unique character across all words.
2. For each pair of consecutive words, find the first index where they differ and add a directed edge from that character in the earlier word to the one in the later word.
3. If no differing character is found and the earlier word is longer than the later one, return "" immediately — the input order is invalid.
4. Run Kahn's algorithm: seed a queue with every character that has in-degree 0, repeatedly pop one, append it to the result, and decrement the in-degree of its neighbors, enqueuing any that drop to 0.
5. If the result contains every character, return it joined as a string; otherwise a cycle exists, so return "".

Complexity

Time: O(C) where C is the total number of characters across all words — Space: O(1), bounded by alphabet size

Code

from collections import defaultdict, deque

def alienOrder(words: list[str]) -> str:
    adjacency = defaultdict(set)
    in_degree = {ch: 0 for word in words for ch in word}

    for first, second in zip(words, words[1:]):
        min_len = min(len(first), len(second))
        found_diff = False
        for i in range(min_len):
            if first[i] != second[i]:
                if second[i] not in adjacency[first[i]]:
                    adjacency[first[i]].add(second[i])
                    in_degree[second[i]] += 1
                found_diff = True
                break
        if not found_diff and len(first) > len(second):
            return ""

    queue = deque([ch for ch in in_degree if in_degree[ch] == 0])
    order = []

    while queue:
        ch = queue.popleft()
        order.append(ch)
        for neighbor in adjacency[ch]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(in_degree):
        return ""
    return "".join(order)

Code Explanation

How the solution above works, piece by piece.

1. Every letter that appears gets an in-degree entry, even if no rule mentions it.
2. Compare each pair of adjacent words. The first position where they differ gives an edge first[i] → second[i]; letters after that tell us nothing.
3. Special case: if a word is a longer prefix-extension placed before its prefix ("abc" before "ab"), the input is invalid → "".
4. Kahn's algorithm: start with letters of in-degree 0, output them, and decrement their successors.
5. If not every letter was output, the rules contain a cycle → "". O(total characters).

Visual Walkthrough

Running it on words = ["wrt", "wrf", "er", "ett", "rftt"]:

Video Explanation

NeetCode — Alien Dictionary, Topological Sort, LeetCode 269