Leetcode 269. Alien Dictionary

Let's understand what we're being asked to do. We have a sorted list of words from an unknown alphabet (not English!), like ['wrt', 'wrf', 'er', 't', 'ett'], and we need to figure out the order of characters in this alien alphabet.

The key insight: words are sorted according to this alien alphabet's rules. So if 'wrt' comes before 'wrf', we know that in this alphabet, 't' comes before 'f' (since that's the first differing character).

Let's trace through: comparing 'wrt' and 'wrf' → first difference is at index 2: 't' vs 'f' → so t < f. Comparing 'wrf' and 'er' → first difference is at index 0: 'w' vs 'e' → so w < e. Comparing 'er' and 't' → first difference is at index 0: 'e' vs 't' → so e < t.

Important constraints: The input is a sorted list according to the alien alphabet. We need to derive the character ordering from these sorted words.

Edge cases to consider: What if there's a cycle in the ordering (impossible to satisfy)? What if one word is a prefix of another but comes after it (like ['abc', 'ab'] - invalid!)? What if some characters never appear in comparisons (they can be in any order)?

Each pair of adjacent words gives us one ordering constraint. If word1 is 'wrt' and word2 is 'wrf', the first differing character tells us 't' must come before 'f' in the alphabet.

This creates a directed relationship: t → f (t comes before f). Collecting all such relationships from adjacent word pairs builds a network of ordering constraints.

These ordering constraints form a directed graph where each edge A → B means 'A comes before B in the alphabet'.

If we can find a linear ordering of characters that respects all these directed edges (no character comes before one of its predecessors), we've found the alien alphabet order! This is exactly what topological sorting solves.

Think of course prerequisites: if 'Calculus requires Algebra' and 'Algebra requires Arithmetic', you need to take them in order: Arithmetic → Algebra → Calculus.

Similarly, if we know w → e, e → t, and t → f, we can deduce the ordering: w, e, t, f. But what if we also had f → w? That creates a cycle (impossible to satisfy) - just like circular course prerequisites make graduation impossible!

Build a directed graph where each edge represents a character ordering constraint derived from adjacent word pairs. For each pair of adjacent words, find the first differing character and add an edge from the character in the first word to the character in the second word. Then perform topological sort using BFS (Kahn's algorithm) with in-degree tracking: repeatedly remove nodes with in-degree 0 and add them to the result. If we can't process all characters (cycle detected) or encounter invalid prefix ordering, return empty string.

from collections import defaultdict, deque
def alien_order(words):
    """
    Infer character ordering from sorted alien dictionary words.
    Returns topological ordering or empty string if invalid.
    """
    # Build adjacency graph and in-degree map
    graph = defaultdict(set)
    in_degree = {char: 0 for word in words for char in word}
    
    # Extract ordering constraints from adjacent word pairs
    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))
        
        # Check for invalid prefix (word1 is prefix of word2 but longer)
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""
        
        # Find first differing character
        for j in range(min_len):
            char1, char2 = word1[j], word2[j]
            if char1 != char2:
                # Add edge if not already present
                if char2 not in graph[char1]:
                    graph[char1].add(char2)
                    in_degree[char2] += 1
                break
    
    # Topological sort using BFS (Kahn's algorithm)
    queue = deque([char for char in in_degree if in_degree[char] == 0])
    result = []
    
    while queue:
        char = queue.popleft()
        result.append(char)
        
        # Reduce in-degree for neighbors
        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check if all characters were processed (no cycle)
    if len(result) != len(in_degree):
        return ""
    
    return "".join(result)

• Topological sort for ordering constraints: When you need to determine a valid ordering from pairwise precedence relationships (A before B, C before D), build a directed graph and use topological sort (BFS with in-degree or DFS) - this problem transforms dictionary ordering into graph edges by comparing adjacent words.
• Character-by-character comparison for edge extraction: Only compare adjacent words in the sorted list, and stop at the first differing character to create a directed edge - continuing past the first difference or comparing non-adjacent words creates invalid constraints that don't follow from the given ordering.
• Cycle detection equals impossible ordering: If topological sort completes but hasn't visited all nodes, or if DFS finds a back edge, the constraints contain a cycle (like A→B→C→A) meaning no valid alphabet exists - return empty string to signal impossibility rather than a partial result.
• Invalid prefix validation: Before building the graph, check if a longer word appears before its prefix (like 'abc' before 'ab') - this violates sorted order and should return empty string immediately, as no alphabet can make a word come before its own prefix in dictionary order.
• In-degree tracking for BFS topological sort: Maintain an in-degree map counting incoming edges for each character, then process nodes with zero in-degree first - this ensures you only add a character to the result after all its predecessors are placed, naturally handling the dependency chain.
• Graph construction from implicit constraints: This pattern applies to any problem where ordering rules are implicit in data arrangement rather than explicit - course prerequisites from enrollment patterns, task scheduling from completion sequences, or dependency resolution from import statements all use the same graph-building approach.