126. Word Ladder II
Given two words (beginWord and endWord), and a dictionary's word list,
find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the word list
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Because we want to record the path, we need to record the parent node for each node, so that at the end, we will find its parent node one by one from the end point, until we find the starting point, and then flip it and add it to the result set.
Probably the process is similar, but the difference is that when deleting a string in the dictionary, this character may be used in another path. It is like this:
A -> C -> D, B->C->D
They will all go through C, and both are the shortest paths. When A is searched for C, and C is deleted from the dictionary. When B is searching for a string with a distance of 1, C is no longer in the dictionary. So what to do? We set up a hash table to store a set of parent nodes of a string, so that C is not in the dictionary and then check the hash table to see if C is in the hash table, if it is, and the parent node level of C Same as B, then B is also added to the parent node combination of C. It can be known that the distance of the parent node set of a string from the starting point must be equal, that is, they are the shortest distance.
Finally, after traversing all the points, use DFS to find all sets from the end point forward.