LeetCode · #269

Alien Dictionary Solution

Given a sorted list of alien words, infer one valid character ordering. If the ordering is inconsistent, return an empty string.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #269

🏗️

Pattern

Topological sort + graph construction

The words are already sorted according to some unknown alphabet. Compare adjacent words to discover precedence rules between characters. Those rules form a directed graph; the alien alphabet is any topological order of that graph.

Example

Input:  ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
// From adjacent comparisons we learn: w < e, e < r, r < t, t < f

Most important edge case:

If a longer word appears before its exact prefix, like ["abc", "ab"], the dictionary order is impossible.
Return "" immediately.

Section Two · Approach 1

DFS Post-order Topological Sort

After building the character graph, run DFS with three-color cycle detection. When a node finishes, append it to an output list. Reverse that list at the end to get one valid character ordering.

Why it works

The first differing character between adjacent words determines the only ordering constraint we can safely infer from that pair. Once all constraints are collected, topological sort returns an order consistent with every edge.

Problem: DFS is correct, but Kahn's BFS is often easier to reason about for this problem because it directly exposes cycles through the final processed-character count. It also makes the "ready characters" concept very concrete.

Section Three · Approach 2

Kahn's BFS Topological Sort

Track every character that appears. Build directed edges only from the first mismatch in each adjacent word pair, and increment the destination's in-degree once per unique edge. Then queue every present character whose in-degree is 0.

Mark every character that appears in any word.
For adjacent words, find the first differing position. Add exactly one edge from word1[i] to word2[i].
If no difference exists and word1 is longer than word2, return empty string.
Run Kahn's BFS.
If the result length is less than the number of present characters, a cycle exists → return empty string.

💡 Mental model: Each character is waiting behind a number of alphabet rules. Characters with zero incoming rules are currently legal to place next. Every time you place one, you remove its outgoing rules and may unlock more characters.

Section Four · Trace

Visual Walkthrough

Trace ["wrt", "wrf", "er", "ett", "rftt"].

Alien Dictionary — graph construction + topo order

Section Five · Implementation

Code — Java & Python

Java — build graph + Kahn's BFS

import java.util.*;

class Solution {
    public String alienOrder(String[] words) {
        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < 26; i++) adj.add(new HashSet<>());

        boolean[] present = new boolean[26];
        int presentCount = 0;
        for (String word : words) {
            for (char ch : word.toCharArray()) {
                int idx = ch - 'a';
                if (!present[idx]) {
                    present[idx] = true;
                    presentCount++;
                }
            }
        }

        int[] indegree = new int[26];
        for (int i = 0; i < words.length - 1; i++) {
            String a = words[i], b = words[i + 1];
            if (a.length() > b.length() && a.startsWith(b)) return "";

            int len = Math.min(a.length(), b.length());
            for (int j = 0; j < len; j++) {
                char ca = a.charAt(j), cb = b.charAt(j);
                if (ca == cb) continue;
                int u = ca - 'a', v = cb - 'a';
                if (adj.get(u).add(v)) indegree[v]++;
                break;
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < 26; i++) {
            if (present[i] && indegree[i] == 0) queue.offer(i);
        }

        StringBuilder order = new StringBuilder();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order.append((char) ('a' + u));
            for (int v : adj.get(u)) {
                if (--indegree[v] == 0) queue.offer(v);
            }
        }

        return order.length() == presentCount ? order.toString() : "";
    }
}

Python — adjacency from adjacent words

from collections import deque

class Solution:
    def alienOrder(self, words: list[str]) -> str:
        present = [False] * 26
        present_count = 0
        for word in words:
            for ch in word:
                idx = ord(ch) - ord('a')
                if not present[idx]:
                    present[idx] = True
                    present_count += 1

        adj = [set() for _ in range(26)]
        indegree = [0] * 26

        for i in range(len(words) - 1):
            a, b = words[i], words[i + 1]
            if len(a) > len(b) and a.startswith(b):
                return ""

            for j in range(min(len(a), len(b))):
                if a[j] == b[j]:
                    continue
                u = ord(a[j]) - ord('a')
                v = ord(b[j]) - ord('a')
                if v not in adj[u]:
                    adj[u].add(v)
                    indegree[v] += 1
                break

        queue = deque(i for i in range(26) if present[i] and indegree[i] == 0)
        order = []

        while queue:
            u = queue.popleft()
            order.append(chr(ord('a') + u))
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)

        return "".join(order) if len(order) == present_count else ""

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS topological sort	O(C + U + E)	O(U + E)	Elegant, but cycle handling is more subtle.
Kahn's BFS ← optimal	O(C + U + E)	O(U + E)	Directly builds the order and detects cycles via processed character count.

What do the symbols mean? C = total number of characters across all words, U = number of unique characters, E = precedence edges inferred from adjacent word pairs.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Single word	Return all unique letters in that word	No ordering constraints exist, but all present letters must appear.
Prefix invalid	`["abc","ab"]` → `""`	A longer word cannot come before its own prefix.
Cycle	Return `""`	Processed character count will be smaller than total present characters.
Duplicate edge	Do not increment indegree twice	Use a set per source character.
No mismatch in adjacent pair	Add no edge	One word being a prefix of the next is valid if the shorter word comes first.

⚠ Common Mistake: Comparing every pair of words instead of only adjacent pairs. The list is already sorted, so only adjacent pairs give safe, necessary ordering information. Non-adjacent comparisons can invent false edges.

← Back to Topological Sort

LearningTree

LC 269 · Alien Dictionary — Solution & Explanation | DSA Guide