Question
Formatted question description: https://leetcode.ca/all/126.html
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
Example 1:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
@tag-backtracking
Algorithm
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.
Code
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Word_Ladder_II {
// iteration bfs
// https://leetcode.com/problems/word-ladder-ii/solution/
public class Solution {
List<List<String>> list = new ArrayList<List<String>>();
public List<List<String>> findLadders(String start, String end, Set<String> dict) {
if (start == null || end == null || dict == null) return list;
dict.add(end); // !!!
Queue<String> q = new LinkedList<String>();
int level = 1;
int currentLevelCount = 1;
int newLevelCount = 0;
boolean found = false;
int foundLevel = -1;
// from end word, to all paths
HashMap<String, ArrayList<ArrayList<String>>> hm = new HashMap<String, ArrayList<ArrayList<String>>>();
q.offer(start);
ArrayList<String> singlePath = new ArrayList<String>();
ArrayList<ArrayList<String>> allPaths = new ArrayList<ArrayList<String>>();
singlePath.add(start);
allPaths.add(singlePath);
hm.put(start, allPaths);
while (!q.isEmpty()) {
String current = q.poll();
currentLevelCount--; // count to mark level
for (int i = 0; i < current.length(); i++) {
char[] array = current.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
array[i] = c;
String each = new String(array);
if (each.equals(end)) {
found = true;
foundLevel = level;
}
if (dict.contains(each)) {
// q.offer(each);
newLevelCount++;
ArrayList<ArrayList<String>> prevAllPaths = hm.get(current);
if (hm.containsKey(each))
allPaths = hm.get(each);
else {
/* @note@note:
enqueue is here. if no path ending at this one, then has to explore in future
if there is path ending at this one, meaning it's been explored already. no need to enqueue
*/
q.offer(each);
allPaths = new ArrayList<ArrayList<String>>();
hm.put(each, allPaths);
}
// @note@note: this if is the key !!! no path for new word, or new word path is one more than previous path
// using this if, the"if visited" check can be removed
// if (allPaths.size() == 0 || prevAllPaths.size() + 1 == allPaths.size()) {
if (allPaths.size() == 0 || prevAllPaths.get(0).size() + 1 == allPaths.get(0).size()) {
for(ArrayList<String> eachPath: prevAllPaths) {
ArrayList<String> newone = new ArrayList<String>(eachPath);
newone.add(each);
allPaths.add(newone);
}
}
}
}
}
// @note@note: also the key, to make sure only find shortest
if (found && foundLevel != level) {
break;
}
// @note: must be after trying the last word of currentLevel, then update
if (currentLevelCount == 0) {
currentLevelCount = newLevelCount;
newLevelCount = 0;
level++;
}
}
if (!found) {
return list;
}
for (ArrayList<String> each: hm.get(end)) {
list.add(each);
}
return list;
}
}
public class Solution_recursion {
private List<String> findPath(String fromWord, String toWord,
Set<String> seenWords) {
if (fromWord.equals(toWord)) {
ArrayList<String> result = new ArrayList<>();
result.add(toWord);
return result;
}
// Find all words that you can go to from fromWord
List<String> nextWords = getNextWords(fromWord, seenWords);
for (String word : nextWords) {
Set<String> newSeenWords = new HashSet<String>(seenWords);
newSeenWords.add(word);
List<String> subPath = findPath(word, toWord, newSeenWords);
if (subPath != null) {
subPath.add(fromWord);
return subPath;
}
}
// There wasn't a path
return null;
}
private final List<String> WORDS = Arrays.asList("head", "heal",
"teal", "tell", "tall", "tail");
private final List<Character> ALPHA = Arrays.asList('a', 'b',
'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z');
private final HashSet<String> DICTIONARY = new HashSet<String>(
WORDS);
private List<String> getNextWords(String fromWord,
Set<String> seenWords) {
List<String> outList = new ArrayList<String>();
StringBuilder builder;
for (int i = 0; i < fromWord.length(); i++) {
builder = new StringBuilder(fromWord);
for (Character j : ALPHA) {
if (j == fromWord.charAt(i)) {
continue;
}
builder.setCharAt(i, j);
String potentialWord = builder.toString();
if (DICTIONARY.contains(potentialWord)
&& !seenWords.contains(potentialWord)) {
outList.add(potentialWord);
}
}
}
return outList;
}
}
}