126. Word Ladder II
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
- Every adjacent pair of words differs by a single letter.
- Every
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].
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"]]
Explanation: There are 2 shortest transformation sequences:
"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 there is no valid transformation sequence.
Solution:
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>();
Set<String> set = new HashSet<>();
for (int i = 0; i < wordList.size(); i++){
set.add(wordList.get(i));
}
if (!set.contains(endWord)){
return result;
}
//Set:
// hot
// dot
// dog
// lot
// log
// cog
Map<String, Integer> map = new HashMap<>();
// <hit, 1>
// <hot, 2>
// <dot, 3>
// <lot, 3>
// <dog, 4>
// <log, 4>
// <cog, 5>
int step = 0;
Deque<String> queue = new ArrayDeque<>();
queue.add(beginWord);
set.remove(beginWord);
map.put(beginWord, 1);
step++;
/* hit hot dot lot dog, <- log <-*/
while(!queue.isEmpty()){
step++;
int size = queue.size();
for (int i = 0; i < size; i++){
String curWord = queue.pollFirst(); // hit, hot , dot/ lot, dog
// int curStep = map.get(curWord); // 1 // 2 // 3 // 4
if (curWord.equals(endWord)){
break;
}
for (int j = 0; j < curWord.length(); j++){
for (char ch = 'a'; ch <= 'z'; ch++){
char[] curWordArray = curWord.toCharArray();
curWordArray[j] = ch;
String replace = new String(curWordArray); // hot // dot// lot // dog//log // cog
if (set.contains(replace)){
set.remove(replace);
map.put(replace, step); // hot, 2
queue.offerLast(replace);
}
}
}
}
}
// <hit, 1>
// <hot, 2>
// <dot, 3>
// <lot, 3>
// <dog, 4>
// <log, 4>
// <cog, 5>
//
// if (map.containsKey(endWord)){
// List<String> curPath = new ArrayList<>();
// curPath.add(beginWord);
// dfs(beginWord, endWord,map, curPath, result);
// }
if (map.containsKey(endWord)){
List<String> curPath = new ArrayList<>();
curPath.add(endWord);
dfs(beginWord, endWord, curPath, map, result);
}
return result;
}
private void dfs(String beginWord, String curWord, List<String> curPath, Map<String, Integer> map, List<List<String>> result){
if (curWord.equals(beginWord)){
List<String> subResult = new ArrayList<String>(curPath);
Collections.reverse(subResult);
result.add(subResult);
}
int curStep = map.get(curWord);
for (int i = 0; i < curWord.length(); i++){
for (char ch = 'a'; ch <= 'z'; ch++){
char[] curWordArray = curWord.toCharArray();
curWordArray[i] = ch;
String next = new String(curWordArray);
if (map.containsKey(next) && map.get(next) + 1 == curStep){
curPath.add(next);
dfs(beginWord, next, curPath, map, result);
curPath.remove(curPath.size() - 1);
}
}
}
}
// private void dfs(String curWord, String endWord, Map<String, Integer> map, List<String> curPath, List<List<String>> result){
// if (curWord.equals(endWord)){
// List<String> subResult = new ArrayList<>(curPath);
// result.add(subResult);
// return;
// }
// int curStep = map.get(curWord);
// for (int i = 0; i < curWord.length(); i++){
// for (char ch = 'a'; ch <= 'z'; ch++){
// char[] curWordArray = curWord.toCharArray();
// curWordArray[i] = ch;
// String next = new String(curWordArray);
// if (map.containsKey(next) && map.get(next) - 1 == curStep){
// curPath.add(next);
// dfs(next, endWord, map, curPath, result);
// curPath.remove(curPath.size() - 1);
// }
// }
// }
// }
}
// TC: O(N * L * 26 + N * W) N wordList.size L word.length
// W 是单词列表中可能的单词转换的平均数量。这个数值取决于单词列表中单词的分布，也就是说，每个单词可以通过改变一个字母转换成多少其他单词。
// SC: O(N)
// 这种dfs写法 可以pass
TLE:
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>();
Set<String> set = new HashSet<>();
for (int i = 0; i < wordList.size(); i++){
set.add(wordList.get(i));
}
if (!set.contains(endWord)){
return result;
}
//Set:
// hot
// dot
// dog
// lot
// log
// cog
Map<String, Integer> map = new HashMap<>();
// <hit, 1>
// <hot, 2>
// <dot, 3>
// <lot, 3>
// <dog, 4>
// <log, 4>
// <cog, 5>
int step = 0;
Deque<String> queue = new ArrayDeque<>();
queue.add(beginWord);
set.remove(beginWord);
map.put(beginWord, 1);
step++;
/* hit hot dot lot dog, <- log <-*/
while(!queue.isEmpty()){
step++;
int size = queue.size();
for (int i = 0; i < size; i++){
String curWord = queue.pollFirst(); // hit, hot , dot/ lot, dog
// int curStep = map.get(curWord); // 1 // 2 // 3 // 4
if (curWord.equals(endWord)){
break;
}
for (int j = 0; j < curWord.length(); j++){
for (char ch = 'a'; ch <= 'z'; ch++){
char[] curWordArray = curWord.toCharArray();
curWordArray[j] = ch;
String replace = new String(curWordArray); // hot // dot// lot // dog//log // cog
if (set.contains(replace)){
set.remove(replace);
map.put(replace, step); // hot, 2
queue.offerLast(replace);
}
}
}
}
}
// <hit, 1>
// <hot, 2>
// <dot, 3>
// <lot, 3>
// <dog, 4>
// <log, 4>
// <cog, 5>
//
if (map.containsKey(endWord)){
List<String> curPath = new ArrayList<>();
curPath.add(beginWord);
dfs(beginWord, endWord,map, curPath, result);
}
if (map.containsKey(endWord)){
List<String> curPath = new ArrayList<>();
curPath.add(endWord);
dfs(beginWord, endWord, curPath, map, result);
}
return result;
}
// private void dfs(String beginWord, String curWord, List<String> curPath, Map<String, Integer> map, List<List<String>> result){
// if (curWord.equals(beginWord)){
// List<String> subResult = new ArrayList<String>(curPath);
// Collections.reverse(subResult);
// result.add(subResult);
// }
// int curStep = map.get(curWord);
// for (int i = 0; i < curWord.length(); i++){
// for (char ch = 'a'; ch <= 'z'; ch++){
// char[] curWordArray = curWord.toCharArray();
// curWordArray[i] = ch;
// String next = new String(curWordArray);
// if (map.containsKey(next) && map.get(next) + 1 == curStep){
// curPath.add(next);
// dfs(beginWord, next, curPath, map, result);
// curPath.remove(curPath.size() - 1);
// }
// }
// }
// }
private void dfs(String curWord, String endWord, Map<String, Integer> map, List<String> curPath, List<List<String>> result){
if (curWord.equals(endWord)){
List<String> subResult = new ArrayList<>(curPath);
result.add(subResult);
return;
}
int curStep = map.get(curWord);
for (int i = 0; i < curWord.length(); i++){
for (char ch = 'a'; ch <= 'z'; ch++){
char[] curWordArray = curWord.toCharArray();
curWordArray[i] = ch;
String next = new String(curWordArray);
if (map.containsKey(next) && map.get(next) - 1 == curStep){
curPath.add(next);
dfs(next, endWord, map, curPath, result);
curPath.remove(curPath.size() - 1);
}
}
}
}
}
// 从beginWord开始, 可以开始的分支(路径) 相对于从endWord开始会多很多. eg会有很多step2
// 但是会很少有map.get(endWord) - 1step的分支
// 第一种严格按照最短路径回溯
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> result = new ArrayList<>(); // 存储所有找到的最短路径
Set<String> set = new HashSet<String>(wordList); //包含 wordList 中所有单词的集合，用于快速查找
Queue<String> queue=new LinkedList<String>(); // 用于 BFS 的队列
Map<String,Integer> map = new HashMap<>(); //映射每个单词到它的步数（即到达该单词的最短路径长度）
// <hit, 1>
// <hot, 2>
// <dot, 3>
// <lot, 3>
// <dog, 4>
// <log, 4>
// <cog, 5>
map.put(beginWord,1);
queue.add(beginWord);
set.remove(beginWord); // avoid duplicate
// BFS
/* hit hot dot lot dog, <- log <-*/
while(!queue.isEmpty()){
String curWord = queue.pollFirst(); // hit, hot , dot/ lot, dog
int curStep = map.get(curWord); // 1 // 2 // 3 // 4
if (curWord.equals(endWord)){
break;
}
for (int i = 0; i < curWord.length(); i++){
for (char ch = 'a'; ch <= 'z'; ch++){
char[] curWordArray = curWord.toCharArray();
curWordArray[i] = ch;
String replace = new String(curWordArray); // hot // dot// lot // dog//log // cog
if (set.contains(replace)){
set.remove(replace);
map.put(replace, curStep + 1); // hot, 2
queue.offerLast(replace);
}
}
}
}
// 如果 map 包含 endWord，则从 endWord 开始使用 DFS 方法寻找所有路径。
if (map.containsKey(endWord)){
List<String> path = new ArrayList<String>();
path.add(endWord);
dfs(beginWord, endWord, path, result, map);
}
return result;
}
public void dfs(String beginWord, String endWord, List<String> path, List<List<String>> result, Map<String, Integer> map){
if (endWord.equals(beginWord)){
List<String> subResult = new ArrayList<String>(path);
Collections.reverse(subResult);
result.add(subResult);
return;
}
String curWord = endWord;
int curStep = map.get(curWord);
for (int i = 0; i < curWord.length(); i++){
for (char ch = 'a'; ch <= 'z'; ch++){
char[] curWordArray = curWord.toCharArray();
curWordArray[i] = ch;
String newWord = new String(curWordArray);
if (map.containsKey(newWord) && map.get(newWord) + 1 == curStep){
path.add(newWord);
dfs(beginWord, newWord, path, result, map);
path.remove(path.size() - 1);
}
}
}
}
}
// TC: O(N * L * 26 + N * W) N wordList.size L word.length
// W 是单词列表中可能的单词转换的平均数量。这个数值取决于单词列表中单词的分布，也就是说，每个单词可以通过改变一个字母转换成多少其他单词。
// SC: O(N)
// 这种dfs写法 可以pass