We are given a sorted dictionary of words in an alien language. The words follow the same lexicographic sorting rules we are familiar with, but the underlying alphabet has a different ordering of letters. Our job is to figure out what that ordering is.

A regular English dictionary works the same way. "apple" comes before "banana" because 'a' comes before 'b'. And "cat" comes before "cup" because when the first letters match ('c' == 'c'), we look at the second letter, and 'a' comes before 'u'. The alien dictionary follows the same comparison logic with a different letter ordering.

Comparing adjacent words in the list therefore extracts ordering rules. Each pair of adjacent words gives us at most one rule about which letter comes before which. Once we have all the rules, we need a total ordering of the letters that satisfies all of them, which is a topological sort problem.

Key Constraints:

Intuition

Comparing adjacent words produces rules of the form "letter A comes before letter B". The problem then reduces to finding a total ordering that satisfies a set of pairwise constraints, and topological sort solves it.

First, compare each pair of adjacent words to extract edges. If word1 is "wrt" and word2 is "wrf", we compare character by character: 'w' == 'w', 'r' == 'r', 't' != 'f'. So we learn that 't' comes before 'f'. We stop at the first difference because the first differing position alone decides the lexicographic comparison; later characters carry no ordering information.

One edge case: if word1 is a prefix of word2 (e.g., "app" before "apple"), the pair is consistent and adds no edge. But if word2 is a prefix of word1 (e.g., "apple" before "app"), the input is invalid because a shorter string must come before a longer one when they share the same prefix.

After extracting all edges, we build a directed graph and run BFS-based topological sort (Kahn's algorithm). We track the in-degree of each node. Start with all nodes that have in-degree 0, process them, reduce the in-degree of their neighbors, and repeat. This also detects invalid input: a node on a cycle can never reach in-degree 0 because one of its predecessors is also stuck on the cycle, so cyclic nodes are never processed. If the result is missing characters, a cycle exists and we return an empty string.

Algorithm

Visualization and Code

The BFS approach is already optimal. Topological sort can also be implemented with DFS, which builds the ordering in reverse post-order and detects cycles through the recursion path itself rather than by counting processed nodes.

Intuition

DFS-based topological sort works differently from BFS. Instead of starting from nodes with no dependencies, we go deep into the graph and fully explore everything that must come after a character before placing that character in the ordering.

When DFS finishes a character (every character reachable from it has been processed), we append it to the result. At that moment, everything that must come after it is already in the list, so the list is built in reverse. Reversing it at the end produces a valid ordering.

Cycle detection uses three states per node: unvisited, visiting (currently on the DFS path), and visited (fully processed). If DFS reaches a node in the "visiting" state, the input contains a cycle and no valid ordering exists.

Algorithm

Visualization and Code