Alien Dictionary LeetCode 269 Complete

LeetCode 269 Alien Dictionary presents you with a list of words sorted in lexicographic order according to an alien language. Your task is to derive the ordering of characters in that alien alphabet and return any valid ordering as a string. If no valid ordering exists — because the constraints form a cycle — return an empty string. If the input is valid but multiple orderings exist, any one of them is accepted.

The core idea is to treat character ordering as a graph problem. By comparing adjacent pairs of words, you can extract directed edges: if word[i] and word[i+1] first differ at position k, then word[i][k] comes before word[i+1][k] in the alien alphabet. These edges form a directed graph, and a valid character ordering is a topological sort of that graph. If the graph has a cycle, no valid ordering exists.

This problem combines string comparison, graph construction, and topological sorting into a single pipeline. Candidates who have not seen it before often get stuck building the graph correctly — particularly missing edge cases during word comparison — and then separately stumble on cycle detection. This guide walks through every layer methodically.

The most dangerous edge case is prefix invalidity: if a longer word appears before a shorter word that is a prefix of it, the input is invalid and you must return an empty string. For example, if "abc" appears before "ab" in the sorted list, no character ordering can explain this — "ab" should always come before "abc" in lexicographic order regardless of the alphabet. Many solutions incorrectly skip this check and produce a wrong answer without a cycle.

Single-word inputs are degenerate but valid. When the list contains only one word, you can extract no ordering constraints from adjacent word comparisons. Every character in that word is part of the alien alphabet and can appear in any order in your output. The correct response is to return all unique characters from the single word in any order.

All identical words present a similar situation: no edges are created because no adjacent pair ever produces a differing character. Every unique character is valid with no ordering constraint. Empty strings in the input are edge cases depending on the problem variant — treat them as words with no characters that contribute no edges and no unique characters to the output.

To build the character ordering graph, iterate through every adjacent pair of words. For each pair, find the first position where the characters differ. The character from the first word at that position must come before the character from the second word in the alien alphabet — add a directed edge from char_a to char_b. Stop comparing after the first differing character; subsequent characters give no ordering information.

A critical implementation detail: initialize the graph and in-degree map with ALL unique characters from ALL words, not just characters that appear in edges. Characters that are present in words but never appear as the first differing character in any adjacent pair have no ordering constraints. They still need to appear in the output — initializing them in the graph ensures they are included even with zero in-degree edges.

The resulting directed graph has at most 26 nodes (one per lowercase letter) and at most one edge per adjacent word pair. Multiple word pairs may contribute edges between the same pair of characters — store edges as a set to avoid duplicate edges, which would corrupt in-degree counts in BFS or cause redundant DFS visits.

Kahn's algorithm performs topological sort using BFS. Start by enqueuing all characters with in-degree zero — these have no prerequisites and can appear first in the ordering. Process the queue: for each dequeued character, append it to the result string, then decrement the in-degree of every character it points to. When a neighbor's in-degree drops to zero, enqueue it.

Cycle detection is built into the process: if the queue empties before all characters have been appended to the result, the remaining characters are part of a cycle. A cycle means some subset of characters each requires another character in the subset to come first — an impossibility. In this case return an empty string. If the result length equals the total number of unique characters, the topological sort succeeded.

BFS naturally produces a valid character ordering because it processes characters in dependency order — no character is added to the result until all characters that must precede it have already been processed. The ordering is not unique in general; when multiple characters have in-degree zero simultaneously, the queue processes them in an arbitrary order, all of which are valid.

The DFS approach uses three-state node coloring to detect cycles and build the ordering simultaneously. WHITE means unvisited, GRAY means currently being explored (in the DFS call stack), and BLACK means fully explored. Initialize all nodes to WHITE. For each unvisited node, launch a DFS.

During DFS, mark the current node GRAY before visiting neighbors. If a neighbor is already GRAY, a back edge has been found — a cycle exists, return empty string. If a neighbor is WHITE, recurse into it. If a neighbor is BLACK, it is already fully processed; skip it. After all neighbors are fully explored, mark the current node BLACK and append it to the result.

Because nodes are appended after all their dependencies are explored (post-order), the result is built in reverse topological order. Reverse the result at the end to obtain a valid ordering. The three-state coloring correctly handles all directed graph topologies including disconnected graphs and graphs with nodes that have no edges — every node is visited exactly once across all DFS calls.

Python BFS implementation uses collections.defaultdict for the adjacency list and collections.deque for the queue. Graph is initialized with all unique characters. Adjacent word pairs populate edges using a set to avoid duplicates. In-degree counts drive the BFS. The solution is approximately 20 lines. Time complexity O(C) where C is the total number of characters across all words — each character is processed once in word comparison, and the graph has at most 26 nodes and at most 26*25 edges.

Python DFS implementation uses a color dictionary initialized to 0 (WHITE) for all chars, 1 (GRAY) during exploration, 2 (BLACK) when done. A nested dfs() function returns False on cycle detection. The result list is reversed after all DFS calls. Both BFS and DFS have identical asymptotic complexity O(C) for graph building plus O(V+E) for traversal where V <= 26 and E <= 26*25, so the bottleneck is always graph construction.

Java implementations mirror the Python logic using HashMap and ArrayDeque for BFS, and HashMap with enum State {WHITE, GRAY, BLACK} for DFS. Java enum states make the coloring explicit and type-safe, reducing the chance of off-by-one bugs in state comparison. Both languages benefit from using a Set to store edges during graph construction to prevent duplicate in-degree increments.

Alien Dictionary is the hardest problem in the topological sort family because it requires constructing the graph from implicit constraints rather than explicit edges. The topological sort itself — once the graph is built — is identical to Course Schedule II (LeetCode 210), which gives you explicit prerequisites as edges. If you can solve Course Schedule II fluently, the only new skill Alien Dictionary requires is the word comparison graph construction and the prefix invalidity edge case.

Reconstruct Itinerary (LeetCode 332) uses a similar directed graph on airport codes and requires finding an Eulerian path rather than a topological ordering. The graph structure is similar but the algorithm (Hierholzer's) is different. Understanding Alien Dictionary solidifies directed graph fluency that transfers directly to these related problems.

For broader DP and graph preparation, the topological sort pattern appears in task scheduling, build systems, and dependency resolution. The BFS Kahn's variant is preferred in production systems because it naturally produces a level-by-level ordering (useful for parallel scheduling) and has a simple cycle detection check. The DFS variant is preferred when you need to detect the specific cycle members rather than just whether a cycle exists.