Leetcode 269. Alien Dictionary and followups
Alien dictionary is a classical problem to test your knowledge of Topological Sorting. I will describe my solution and some possible followups here.
First, we need to build the graph. I think this should be very straightforward if you are at the level of hard problems.
- Get all characters used in the dictionary, which will be nodes. But this dictionary will also be used in the traverse.
- Extract edges from the input. Just find the same prefix and use the first different character.
- Perform Topological sort.
There are two types of topological sort. DFS and BFS. The DFS method can be found in CLRS. The BFS version is a homework question in that section. In a word, DFS traces down the tree and output the node in post order. BFS tracks the in-degrees. For each node with zero in-degree, output it and remove it from the graph.
For this question, we also need to test whether we can get a valid topological sorting result. In DFS, we do this by testing whether we will encounter a “back edge”, which points back to one of its parent. To do this, we can use a hashset to record current ancestors. In BFS, we just test the final result size. If the final result cannot contain all nodes, it is invalid.
So we can get the DFS code:
You can see that I used a hashmap as the visited map and dictionary. If you use DFS, the result should be reversed because we are always getting the last element.
And here is the BFS code:
Now we do not need the visited map, but we need to track the in-degrees. Actually you can also use a hashset to maintain zero degree nodes. But it does not change the complexity.
A popular followup would be: can you print all valid solutions?
Actually, this problem is UVA 872: Ordering. To print all possibilities, we need to use backtracking to test all traverse paths. So we will use BFS topological sort to get nodes, and use backtracking to print all paths. One trick is set the in-degree of visited node as -1.
