Introduction to Alien Dictionary Problem
The Alien Dictionary problem is a fascinating algorithmic challenge that frequently appears in technical interviews at major tech companies. It tests your understanding of graph theory, topological sorting, and string manipulation. In this tutorial, we'll explore how to solve this problem efficiently using Python.
What is the Alien Dictionary Problem?
The Alien Dictionary problem involves deciphering the alphabetical order of characters in an alien language. You're given a list of words from this alien language, and your task is to determine the order of characters in their alphabet. The words are sorted according to this alien alphabet, and you need to reconstruct the character order based on the given word list.
Why It Matters
This problem is significant for several reasons:
- It tests your ability to model real-world problems using graphs
- It requires knowledge of topological sorting, a fundamental algorithm for ordering elements with dependencies
- It demonstrates your skills in handling edge cases and constraints
- It's a common interview question at companies like Google, Facebook, and Amazon
Understanding the 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 according to the rules of this new language. You need to return a string containing all unique characters in the correct order. If no valid ordering exists (e.g., due to a cycle in the dependencies), return an empty string.
Examples
Let's look at a few examples to understand the problem better:
Example 1:
Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
In this example, by comparing adjacent words, we can deduce:
- From "wrt" and "wrf": 't' comes before 'f'
- From "wrf" and "er": 'w' comes before 'e'
- From "er" and "ett": 'r' comes before 't'
- From "ett" and "rftt": 'e' comes before 'r'
Combining these rules, we get the order: "wertf"
Example 2:
Input: words = ["z", "x"]
Output: "zx"
From "z" and "x", we can deduce that 'z' comes before 'x'.
Example 3:
Input: words = ["z", "x", "z"]
Output: ""
This is an invalid case because we have a cycle: 'z' comes before 'x', but 'x' also comes before 'z'. Hence, no valid ordering exists.
Approach to Solve the Problem
Graph Representation
The key insight is to model this problem as a directed graph:
- Each unique character is a node in the graph
- A directed edge from character A to character B means A comes before B in the alien alphabet
- We can extract these edges by comparing adjacent words in the list
By comparing adjacent words, we can find the first differing character, which gives us a direct relationship between those characters in the alien alphabet.
Topological Sort
Once we have our graph, we need to find a topological ordering of the nodes. Topological sorting arranges the nodes in a directed acyclic graph (DAG) such that for every directed edge (u, v), node u comes before node v in the ordering.
There are two main approaches to topological sorting:
- Kahn's algorithm (BFS-based)
- Depth-First Search (DFS) based approach
In this tutorial, we'll use Kahn's algorithm, which is more intuitive for this problem.
Step-by-Step Solution
Building the Graph
First, we need to build our graph by comparing adjacent words:
def build_graph(words):
# Initialize graph and in-degree count
graph = {}
in_degree = {}
# Initialize all characters in the graph
for word in words:
for char in word:
if char not in graph:
graph[char] = set()
in_degree[char] = 0
# Build the graph by comparing adjacent words
for i in range(len(words) - 1):
word1, word2 = words[i], words[i + 1]
min_len = min(len(word1), len(word2))
# Check if word2 is a prefix of word1 (invalid case)
if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
return None, None
# Find the first different character
for j in range(min_len):
if word1[j] != word2[j]:
if word2[j] not in graph[word1[j]]:
graph[word1[j]].add(word2[j])
in_degree[word2[j]] += 1
break
return graph, in_degree
Detecting Cycles
If there's a cycle in our graph, no valid ordering exists. We can detect cycles during the topological sort by checking if we've processed all nodes. If not all nodes are processed, there's a cycle.
Implementing Topological Sort
Now, let's implement Kahn's algorithm for topological sorting:
from collections import deque
def topological_sort(graph, in_degree):
# Initialize a queue with all nodes having in-degree 0
queue = deque([char for char in in_degree if in_degree[char] == 0])
result = []
while queue:
char = queue.popleft()
result.append(char)
# Decrease in-degree of neighbors
for neighbor in graph[char]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If result doesn't contain all characters, there's a cycle
if len(result) != len(graph):
return ""
return "".join(result)
Complete Solution
Python Implementation
Now, let's combine everything into a complete solution:
from collections import deque
def alien_order(words):
# Build the graph
graph = {}
in_degree = {}
# Initialize all characters in the graph
for word in words:
for char in word:
if char not in graph:
graph[char] = set()
in_degree[char] = 0
# Build the graph by comparing adjacent words
for i in range(len(words) - 1):
word1, word2 = words[i], words[i + 1]
min_len = min(len(word1), len(word2))
# Check if word2 is a prefix of word1 (invalid case)
if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
return ""
# Find the first different character
for j in range(min_len):
if word1[j] != word2[j]:
if word2[j] not in graph[word1[j]]:
graph[word1[j]].add(word2[j])
in_degree[word2[j]] += 1
break
# Topological sort using Kahn's algorithm
queue = deque([char for char in in_degree if in_degree[char] == 0])
result = []
while queue:
char = queue.popleft()
result.append(char)
# Decrease in-degree of neighbors
for neighbor in graph[char]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# If result doesn't contain all characters, there's a cycle
if len(result) != len(graph):
return ""
return "".join(result)
Testing the Solution
Let's test our solution with the examples we discussed earlier:
# Test cases
test_cases = [
["wrt", "wrf", "er", "ett", "rftt"], # Expected: "wertf"
["z", "x"], # Expected: "zx"
["z", "x", "z"], # Expected: ""
["abc", "ab"], # Expected: "" (invalid case)
["a", "b", "c", "a"] # Expected: "" (cycle)
]
for i, words in enumerate(test_cases):
result = alien_order(words)
print(f"Test case {i+1}: {words}")
print(f"Result: '{result}'")
print()
Output:
Test case 1: ['wrt', 'wrf', 'er', 'ett', 'rftt']
Result: 'wertf'
Test case 2: ['z', 'x']
Result: 'zx'
Test case 3: ['z', 'x', 'z']
Result: ''
Test case 4: ['abc', 'ab']
Result: ''
Test case 5: ['a', 'b', 'c', 'a']
Result: ''
Best Practices
Edge Cases
When solving the Alien Dictionary problem, it's crucial to handle these edge cases:
- Empty input: Return an empty string if the input list is empty
- Single word: Return the unique characters in any order if there's only one word
- Invalid word order: If a longer word comes before its prefix (e.g., "abc" before "ab"), return an empty string
- Cycles: Detect cycles in the graph and return an empty string if found
- Multiple valid orderings: Any valid topological order is acceptable
Optimization
Here are some optimization strategies for the Alien Dictionary problem:
- Use sets for graph edges to avoid duplicate edges
- Use a deque for the queue in BFS to achieve O(1) operations
- Early termination if an invalid case is detected
- Consider using DFS-based topological sort for certain graph structures
Time and Space Complexity
Let's analyze the complexity of our solution:
- Time Complexity: O(C), where C is the total number of characters in all words. We process each character once when building the graph and once during topological sort.
- Space Complexity: O(1) or O(U), where U is the number of unique characters. Since the alphabet size is fixed (26 for English), the space is constant. However, for a general case with any characters, it's O(U).
Alternative Approach: DFS-based Topological Sort
While we used Kahn's algorithm (BFS-based) in our solution, let's also look at a DFS-based approach for topological sorting:
def alien_order_dfs(words):
# Build the graph
graph = {}
for word in words:
for char in word:
if char not in graph:
graph[char] = set()
# Build the graph by comparing adjacent words
for i in range(len(words) - 1):
word1, word2 = words[i], words[i + 1]
min_len = min(len(word1), len(word2))
# Check if word2 is a prefix of word1 (invalid case)
if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
return ""
# Find the first different character
for j in range(min_len):
if word1[j] != word2[j]:
graph[word1[j]].add(word2[j])
break
# DFS-based topological sort
visited = {} # 0: unvisited, 1: visiting, 2: visited
result = []
def dfs(char):
if visited.get(char, 0) == 1:
return False # Cycle detected
if visited.get(char, 0) == 2:
return True # Already processed
visited[char] = 1 # Mark as visiting
for neighbor in graph[char]:
if not dfs(neighbor):
return False
visited[char] = 2 # Mark as visited
result.append(char)
return True
# Process all characters
for char in graph:
if visited.get(char, 0) == 0:
if not dfs(char):
return ""
# Reverse the result to get the correct order
return "".join(reversed(result))
The DFS-based approach uses three states for each node: unvisited, visiting, and visited. This helps in detecting cycles during the traversal.
Conclusion
The Alien Dictionary problem is an excellent example of how graph theory and topological sorting can be applied to solve real-world problems. By modeling the character relationships as a directed graph and applying topological sort, we can efficiently determine the order of characters in an alien alphabet. The key steps involve building the graph by comparing adjacent words, detecting cycles, and performing topological sort using either BFS (Kahn's algorithm) or DFS. Remember to handle edge cases like invalid word orders and cycles properly. With the approaches and best practices outlined in this tutorial, you should now be well-equipped to tackle the Alien Dictionary problem in your coding interviews or projects.