Introduction to the Alien Dictionary Problem
The Alien Dictionary problem is a popular coding interview question that combines graph theory with topological sorting. In this problem, you are given a list of words from an alien language, where the words are sorted lexicographically according to the alien language's rules. Your task is to determine the order of characters in that alien alphabet.
This problem tests your understanding of directed graphs, cycle detection, and topological sorting — all fundamental concepts in computer science. It frequently appears in interviews at major tech companies because it elegantly combines multiple algorithmic concepts into a single problem.
Problem Statement
Given a sorted list of words from an alien language, find the order of characters in that language. The words are sorted lexicographically based on the alien alphabet's ordering rules. You need to return a string representing the character order. If no valid ordering exists (for example, due to a cycle in the character relationships), return an empty string.
For example, given the input ["wrt", "wrf", "er", "ett", "rftt"], the correct output would be "wertf". This means in the alien language, 'w' comes before 'e', 'e' comes before 'r', 't' comes before 'f', and so on.
Why the Alien Dictionary Matters
The Alien Dictionary problem is more than just an interview exercise. It has real-world applications and teaches several important concepts:
- Topological Sorting: This is used in task scheduling, build systems, dependency resolution, and course prerequisite planning.
- Graph Construction: Learning to extract graph structure from seemingly unrelated data is a valuable skill.
- Cycle Detection: Detecting cycles in directed graphs is crucial for deadlock detection, dependency analysis, and more.
- Data Validation: The problem teaches you to validate whether a given input can produce a valid result, which is important in many real-world systems.
Understanding how to solve this problem gives you a strong foundation in graph algorithms that you can apply to many other scenarios, from build pipelines to package managers.
Understanding the Approach
The key insight is that by comparing adjacent words in the sorted list, we can extract ordering relationships between characters. When two adjacent words differ, the first differing character tells us which character comes before the other in the alien alphabet.
Step 1: Extract Character Relationships
For each pair of adjacent words, find the first position where the characters differ. The character from the first word comes before the character from the second word. This gives us a directed edge in our graph.
For example, comparing "wrt" and "wrf", the first difference is at index 2: 't' vs 'f'. This tells us 't' comes before 'f' in the alien alphabet.
Step 2: Build a Directed Graph
We construct a directed graph where each node is a character, and each edge represents a "comes before" relationship. We also track the in-degree of each node — the number of edges pointing to it.
Step 3: Topological Sort Using Kahn's Algorithm
We use Kahn's algorithm for topological sorting. This involves repeatedly finding nodes with zero in-degree, adding them to our result, and removing their outgoing edges. If we can process all nodes, we have a valid ordering. If some nodes remain unprocessed, there's a cycle, and no valid ordering exists.
Step 4: Handle Edge Cases
Several edge cases need attention:
- A word that is a prefix of the previous word but longer (e.g.,
["abc", "ab"]) is invalid because a shorter word should come first. - Single-word input where we just need to return the unique characters in any order.
- Duplicate characters within the same word don't create self-loops.
Step-by-Step Implementation in Go
Now let's implement the solution in Go. We'll build it up step by step.
Defining the Data Structures
First, we need to represent our graph. We'll use a map to store adjacency lists and another map to track in-degrees.
package main
import (
"fmt"
)
// alienOrder finds the order of characters in an alien language
func alienOrder(words []string) string {
// adjacency list: char -> set of chars that come after it
graph := make(map[byte]map[byte]bool)
// in-degree: char -> number of chars that come before it
inDegree := make(map[byte]int)
// Initialize graph with all unique characters
for _, word := range words {
for i := 0; i < len(word); i++ {
c := word[i]
if _, exists := graph[c]; !exists {
graph[c] = make(map[byte]bool)
inDegree[c] = 0
}
}
}
This initialization ensures that every character that appears in any word is represented in our graph, even if it has no edges. This is important because characters that appear only once still need to be in our final ordering.
Building the Graph from Word Pairs
Next, we compare each pair of adjacent words to extract ordering relationships:
// Compare adjacent words to find character ordering
for i := 0; i < len(words)-1; i++ {
word1 := words[i]
word2 := words[i+1]
// Check for invalid case: word1 is a prefix of word2
// but word1 is longer (invalid ordering)
if len(word1) > len(word2) &&
word1[:len(word2)] == word2 {
return ""
}
// Find first differing character
minLen := len(word1)
if len(word2) < minLen {
minLen = len(word2)
}
for j := 0; j < minLen; j++ {
char1 := word1[j]
char2 := word2[j]
if char1 != char2 {
// char1 comes before char2
if !graph[char1][char2] {
graph[char1][char2] = true
inDegree[char2]++
}
break // only the first difference matters
}
}
}
Notice the prefix check: if word1 is longer than word2 but word2 is a prefix of word1, this is an invalid ordering. For example, ["abc", "ab"] is invalid because "ab" should come before "abc" in any valid lexicographic ordering.
We also use a set (implemented as map[byte]bool) for the adjacency list to avoid adding duplicate edges, which would incorrectly inflate the in-degree count.
Performing Topological Sort
Now we implement Kahn's algorithm for topological sorting:
// Kahn's algorithm for topological sort
// Start with all nodes that have zero in-degree
queue := []byte{}
for char, degree := range inDegree {
if degree == 0 {
queue = append(queue, char)
}
}
var result []byte
for len(queue) > 0 {
// Dequeue a character with zero in-degree
curr := queue[0]
queue = queue[1:]
result = append(result, curr)
// Reduce in-degree of all neighbors
for neighbor := range graph[curr] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
// If we processed all characters, return the order
// Otherwise, there's a cycle and no valid ordering exists
if len(result) == len(graph) {
return string(result)
}
return ""
}
The algorithm works by maintaining a queue of nodes with zero in-degree. We repeatedly remove a node from the queue, add it to our result, and decrement the in-degree of all its neighbors. If a neighbor's in-degree reaches zero, it's added to the queue. If the final result contains all nodes, we have a valid topological order. If not, there's a cycle in the graph.
The Complete Solution
Here is the complete, ready-to-run solution:
package main
import (
"fmt"
)
func alienOrder(words []string) string {
// adjacency list: char -> set of chars that come after it
graph := make(map[byte]map[byte]bool)
// in-degree: char -> number of chars that come before it
inDegree := make(map[byte]int)
// Initialize graph with all unique characters
for _, word := range words {
for i := 0; i < len(word); i++ {
c := word[i]
if _, exists := graph[c]; !exists {
graph[c] = make(map[byte]bool)
inDegree[c] = 0
}
}
}
// Compare adjacent words to find character ordering
for i := 0; i < len(words)-1; i++ {
word1 := words[i]
word2 := words[i+1]
// Check for invalid case: word1 is longer and word2
// is a prefix of word1
if len(word1) > len(word2) &&
word1[:len(word2)] == word2 {
return ""
}
// Find first differing character
minLen := len(word1)
if len(word2) < minLen {
minLen = len(word2)
}
for j := 0; j < minLen; j++ {
char1 := word1[j]
char2 := word2[j]
if char1 != char2 {
if !graph[char1][char2] {
graph[char1][char2] = true
inDegree[char2]++
}
break
}
}
}
// Kahn's algorithm for topological sort
queue := []byte{}
for char, degree := range inDegree {
if degree == 0 {
queue = append(queue, char)
}
}
var result []byte
for len(queue) > 0 {
curr := queue[0]
queue = queue[1:]
result = append(result, curr)
for neighbor := range graph[curr] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
if len(result) == len(graph) {
return string(result)
}
return ""
}
func main() {
// Test case 1: Standard example
words1 := []string{"wrt", "wrf", "er", "ett", "rftt"}
result1 := alienOrder(words1)
fmt.Printf("Input: %v\nOutput: %s\n\n", words1, result1)
// Test case 2: Simple two-character ordering
words2 := []string{"z", "x"}
result2 := alienOrder(words2)
fmt.Printf("Input: %v\nOutput: %s\n\n", words2, result2)
// Test case 3: Invalid ordering (cycle)
words3 := []string{"z", "x", "z"}
result3 := alienOrder(words3)
fmt.Printf("Input: %v\nOutput: %s\n\n", words3, result3)
// Test case 4: Single word
words4 := []string{"abc"}
result4 := alienOrder(words4)
fmt.Printf("Input: %v\nOutput: %s\n\n", words4, result4)
// Test case 5: Invalid prefix case
words5 := []string{"abc", "ab"}
result5 := alienOrder(words5)
fmt.Printf("Input: %v\nOutput: %s\n\n", words5, result5)
}
Expected Output
Input: [wrt wrf er ett rftt]
Output: wertf
Input: [z x]
Output: zx
Input: [z x z]
Output:
Input: [abc]
Output: abc
Input: [abc ab]
Output:
Note that for test case 4 with a single word, the output could be any permutation of the unique characters since there are no ordering constraints. The output "abc" is one valid possibility.
Complexity Analysis
Understanding the time and space complexity of this solution is important:
- Time Complexity: O(C) where C is the total number of characters across all words. We iterate through all characters to build the graph, and the topological sort processes each character and edge once. The number of edges is at most O(U^2) where U is the number of unique characters, but in practice it's bounded by the number of adjacent word pairs times the minimum word length.
- Space Complexity: O(U + E) where U is the number of unique characters and E is the number of edges. We store the adjacency list and in-degree map, both of which are proportional to the number of unique characters and edges.
In the worst case, if all characters are unique and every pair of adjacent words contributes an edge, the space complexity is O(U^2) for the adjacency list. However, in most practical cases, the number of edges is much smaller.
Best Practices
1. Always Handle Edge Cases
The Alien Dictionary problem has several tricky edge cases. Always test for:
- Empty input or single-word input
- Words where one is a prefix of another (invalid if the longer one comes first)
- Cyclic dependencies (e.g.,
["a", "b", "a"]) - Words with repeated characters
- All words being identical
2. Use Sets to Avoid Duplicate Edges
When building the graph, use a set data structure for the adjacency list to prevent adding duplicate edges. Without this, the in-degree count could be incorrect, leading to wrong results. In Go, we use map[byte]bool as a set.
3. Initialize All Nodes Before Adding Edges
Make sure every unique character is initialized in the graph before adding edges. Characters that appear in the input but have no ordering constraints still need to be included in the final result. Forgetting this step is a common bug.
4. Validate Input Early
Check for the invalid prefix case as early as possible. If word1 is longer than word2 and word2 is a prefix of word1, return an empty string immediately. This saves unnecessary computation.
5. Consider Using a More Efficient Queue
In the implementation above, we use a slice as a queue with queue[0] and queue[1:]. This is O(n) for dequeue operations. For better performance with large inputs, consider using container/list for an O(1) dequeue:
import "container/list"
// Replace the queue logic with:
queue := list.New()
for char, degree := range inDegree {
if degree == 0 {
queue.PushBack(char)
}
}
var result []byte
for queue.Len() > 0 {
front := queue.Front()
queue.Remove(front)
curr := front.Value.(byte)
result = append(result, curr)
for neighbor := range graph[curr] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue.PushBack(neighbor)
}
}
}
6. Write Comprehensive Tests
Always write tests covering normal cases, edge cases, and invalid inputs. Here's an example test function:
package main
import "testing"
func TestAlienOrder(t *testing.T) {
tests := []struct {
name string
words []string
expected string
}{
{
name: "standard case",
words: []string{"wrt", "wrf", "er", "ett", "rftt"},
expected: "wertf",
},
{
name: "two words",
words: []string{"z", "x"},
expected: "zx",
},
{
name: "cycle detection",
words: []string{"z", "x", "z"},
expected: "",
},
{
name: "single word",
words: []string{"abc"},
expected: "abc",
},
{
name: "invalid prefix",
words: []string{"abc", "ab"},
expected: "",
},
{
name: "empty input",
words: []string{},
expected: "",
},
{
name: "same words",
words: []string{"a", "a"},
expected: "a",
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
result := alienOrder(tt.words)
// For cases with multiple valid orderings,
// we check if the result is valid
if tt.expected != "" && result != tt.expected {
// Some test cases may have multiple valid answers
// For strict testing, validate the ordering instead
if !isValidOrder(result, tt.words) {
t.Errorf("got %s, expected %s", result, tt.expected)
}
}
if tt.expected == "" && result != "" {
t.Errorf("got %s, expected empty string", result)
}
})
}
}
// isValidOrder checks if the given order is consistent
// with the word list
func isValidOrder(order string, words []string) bool {
charPos := make(map[byte]int)
for i := 0; i < len(order); i++ {
charPos[order[i]] = i
}
for i := 0; i < len(words)-1; i++ {
w1, w2 := words[i], words[i+1]
minLen := len(w1)
if len(w2) < minLen {
minLen = len(w2)
}
for j := 0; j < minLen; j++ {
if w1[j] != w2[j] {
if charPos[w1[j]] > charPos[w2[j]] {
return false
}
break
}
}
}
return true
}
Alternative Approach: DFS-Based Topological Sort
While Kahn's algorithm (BFS) is the most intuitive approach, you can also solve this using DFS-based topological sort. In the DFS approach, you perform a depth-first traversal and add nodes to the result in reverse post-order. You also need to detect cycles using a "visiting" state.
func alienOrderDFS(words []string) string {
graph := make(map[byte]map[byte]bool)
// Initialize all characters
for _, word := range words {
for i := 0; i < len(word); i++ {
if _, exists := graph[word[i]]; !exists {
graph[word[i]] = make(map[byte]bool)
}
}
}
// Build edges
for i := 0; i < len(words)-1; i++ {
w1, w2 := words[i], words[i+1]
if len(w1) > len(w2) && w1[:len(w2)] == w2 {
return ""
}
minLen := len(w1)
if len(w2) < minLen {
minLen = len(w2)
}
for j := 0; j < minLen; j++ {
if w1[j] != w2[j] {
graph[w1[j]][w2[j]] = true
break
}
}
}
// States: 0 = unvisited, 1 = visiting, 2 = visited
state := make(map[byte]int)
var result []byte
var hasCycle bool
var dfs func(char byte)
dfs = func(char byte) {
if hasCycle {
return
}
state[char] = 1 // visiting
for neighbor := range graph[char] {
if state[neighbor] == 1 {
hasCycle = true // back edge = cycle
return
}
if state[neighbor] == 0 {
dfs(neighbor)
}
}
state[char] = 2 // visited
result = append([]byte{char}, result...) // prepend
}
for char := range graph {
if state[char] == 0 {
dfs(char)
}
}
if hasCycle {
return ""
}
return string(result)
}
The DFS approach has the same time and space complexity but uses recursion. Be cautious of stack overflow with very large inputs. The BFS approach is generally preferred for its iterative nature and easier cycle detection.
Common Pitfalls and How to Avoid Them
Forgetting to Include All Characters
A common mistake is only adding characters that appear in edges. Characters that appear in the input but have no ordering constraints must still be in the output. Always initialize all unique characters in the graph first.
Not Checking the Prefix Case
The case where a longer word comes before a shorter word that is its prefix is invalid. For example, ["abcd", "abc"] should return an empty string. Many solutions miss this check.
Adding Duplicate Edges
If the same character pair appears in multiple adjacent word comparisons, you might add duplicate edges. This inflates the in-degree count and breaks the topological sort. Using a set for the adjacency list prevents this.
Not Breaking After First Difference
When comparing two words, only the first differing character pair gives us ordering information. Characters after the first difference don't provide any ordering constraints. Always break out of the comparison loop after finding the first difference.
Conclusion
The Alien Dictionary problem is an excellent exercise in graph construction and topological sorting. By comparing adjacent words to extract character ordering relationships, building a directed graph, and applying Kahn's algorithm for topological sort, we can determine the alien alphabet's character order. The solution elegantly handles cycle detection through the in-degree mechanism, returning an empty string when no valid ordering exists. Key implementation details include initializing all unique characters in the graph, using sets to avoid duplicate edges, checking for the invalid prefix case, and breaking after the first differing character when comparing words. Whether you use the BFS-based Kahn's algorithm or a DFS-based approach, the fundamental concepts remain the same. Mastering this problem gives you a solid foundation in graph algorithms that you can apply to dependency resolution, task scheduling, build systems, and many other real-world scenarios. Practice with various edge cases, write comprehensive tests, and you'll be well-prepared to tackle this problem and similar graph-based challenges in your coding interviews and projects.