What is being done here is very similar to Problem 210, #366. I recommend checking that out first before moving on to this.
When we have some words like ["a", "b", "c", "cx", "cy"], what we can infer from here is that: c comes after b, b comes after a, y comes after x. This all should remind us of the successor relationship from directed graphs. So, if we can create a graph of these letter relationships, we can just apply topological sorting to it to get the lexicographical ordering.
While creating the graph, if some words after one word is it prefix, it means that this dictionary is not valid and we can safely shortcut our way to returning false (an empty string). Otherwise, we create relationships by comparing the first different character. We would only compare 'x' and 'y' in the strings "asdxefg", "asdyokt". After creating the graph, there are 2 main methods of topologically sorting it:
BFS and Kahn's Algorithm
We place the letters without predecessors (inDegree[letter] == 0) into a queue. We poll them and add their children, if their children now have a inDegree of 0. We also prevent the addition of the same letters as the in-degrees of some letters will go down to negative and hence be not 0. Eventually, we return this ordering we get by applying this method if and only if the amount of letters we have traversed is equal to the amount of letters in the dictionary. Otherwise, this implies that in-degrees of some letters weren't reduced to 0 and hence there was a cycle. If so, we return the empty string as requested.
DFS
This one is nearly the same as the DFS solution in Course Schedule II. We just place the letters in the ordering from the back as DFS recursion-stack moves back.
Resolves: #241
Algorithm:
What is being done here is very similar to Problem 210, #366. I recommend checking that out first before moving on to this. When we have some words like
["a", "b", "c", "cx", "cy"], what we can infer from here is that: c comes after b, b comes after a, y comes after x. This all should remind us of the successor relationship from directed graphs. So, if we can create a graph of these letter relationships, we can just apply topological sorting to it to get the lexicographical ordering. While creating the graph, if some words after one word is it prefix, it means that this dictionary is not valid and we can safely shortcut our way to returning false (an empty string). Otherwise, we create relationships by comparing the first different character. We would only compare'x'and'y'in the strings"asdxefg", "asdyokt". After creating the graph, there are 2 main methods of topologically sorting it:BFS and Kahn's Algorithm
We place the letters without predecessors (
inDegree[letter] == 0) into a queue. We poll them and add their children, if their children now have a inDegree of 0. We also prevent the addition of the same letters as the in-degrees of some letters will go down to negative and hence be not 0. Eventually, we return this ordering we get by applying this method if and only if the amount of letters we have traversed is equal to the amount of letters in the dictionary. Otherwise, this implies that in-degrees of some letters weren't reduced to 0 and hence there was a cycle. If so, we return the empty string as requested.DFS
This one is nearly the same as the DFS solution in Course Schedule II. We just place the letters in the ordering from the back as DFS recursion-stack moves back.