Alien Dictionary
Problem Statement
There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you. You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language. Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.
Constraints:
- 1 <= words.length <= 100
- 1 <= words[i].length <= 100
- words[i] consists of only lowercase English letters.
- words is sorted lexicographically according to the alien language.
Input Format:
- An array of strings words, representing a sorted dictionary in the alien language
Output Format:
- Return a string representing the order of letters in the alien language. If no valid order exists, return an empty string.
Examples:
Example 1:
Input:
words = ["wrt","wrf","er","ett","rftt"]
Output:
"wertf"
Explanation:
From the first two words, we know 't' comes after 'r'. From the second and third words, we know 'w' comes before 'e'. From the third and fourth words, we know 'r' comes before 't'. From the fourth and fifth words, we know 'e' comes before 'r'. Ordering these relationships gives us the sequence 'wertf'.
Example 2:
Input:
words = ["z","x"]
Output:
"zx"
Explanation:
From the first two words, we know 'z' comes before 'x'.
Example 3:
Input:
words = ["z","x","z"]
Output:
""
Explanation:
The third word "z" breaks the order since the first word "z" should come after the second word "x".
Solutions
Topological Sort using BFS (Kahn's Algorithm)
Build a graph where characters are nodes and edges represent ordering relations. Use Kahn's algorithm to perform topological sorting on the graph, which will give us the correct order of characters.
Topological Sort using DFS
Build a graph and use depth-first search to detect cycles and perform topological sorting. This approach builds the result in reverse order.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Create a graph of character relations: w->e, t->f, e->r, r->t
- Perform topological sort on the graph
- Start with characters that have no incoming edges: w
- Remove w from graph, add to result: result = 'w'
- This makes e have no incoming edges, add to result: result = 'we'
- Continue: result = 'wer'
- Continue: result = 'wert'
- Continue: result = 'wertf'
- Final order: 'wertf'
Hints
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Video Tutorial
Alien Dictionary - Topological Sort Solution
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the directed graph of character relations, then step through the topological sort algorithm to find the ordering.
Key visualization elements:
- current node
- dependency edges
- sorting progress
Implementation Notes
This is a classic application of topological sorting on a directed graph. The key insight is recognizing how to construct the character ordering graph from the provided dictionary words.