Alien Dictionary - Solution & Explanation

Problem Overview: You’re given a list of words already sorted according to an unknown alien language. Your task is to reconstruct the ordering of characters in that language. If the ordering is invalid (for example, a prefix rule violation), return an empty string.

Approach 1: Graph Construction + Kahn's Algorithm (BFS Topological Sort) (Time: O(V + E), Space: O(V + E))

Model the problem as a directed graph where each character is a node. Compare adjacent words in the sorted list and find the first position where they differ. That difference reveals the ordering rule: char1 -> char2. Build an adjacency list and track indegrees for each character. Then run a Breadth-First Search using Kahn’s algorithm: push all characters with indegree 0 into a queue and process them while decreasing neighbors' indegrees. The result forms the alien character order. If you process fewer nodes than exist, a cycle exists and the ordering is invalid.

This approach is preferred because BFS naturally produces a valid topological ordering while detecting cycles through leftover nodes. It also cleanly handles disconnected components in the graph.

Approach 2: Graph Construction + DFS Topological Sort (Time: O(V + E), Space: O(V + E))

The graph construction step is identical: compare adjacent words and add a directed edge for the first mismatching characters. Instead of using a queue, run a Depth-First Search to produce a topological ordering. Track node states (unvisited, visiting, visited). If DFS reaches a node marked as visiting, a cycle exists and the dictionary is invalid. After exploring all neighbors, push the node into a result stack. Reverse the stack to get the final character order.

This method is common in classic topological sort implementations. It’s slightly more compact but requires careful cycle detection with recursion state tracking.

Key Edge Case: Invalid Prefix

If a longer word appears before its prefix (for example "abc" before "ab"), the ordering is impossible. Detect this while comparing adjacent words. If the first word starts with the second but is longer, return an empty string immediately.

Recommended for interviews: Build the character graph and run BFS with Kahn’s algorithm. Interviewers expect you to recognize the hidden topological sorting problem. Showing how to extract ordering constraints from adjacent words demonstrates strong graph modeling skills, while the BFS solution shows you understand cycle detection and dependency ordering.