![LeetCode-126. Word Ladder II [C++][Java]](http://www.mshxw.com/aiimages/31/731590.png "LeetCode-126. Word Ladder II [C++][Java]")
相关题目：
LeetCode-127. Word Ladder [C++][Java]_贫道绝缘子的博客-CSDN博客Atransformation sequencefrom wordbeginWordto wordendWordusing a dictionarywordListis a sequence of wordsbeginWord -> s1-> s2-> ... -> sk , return shortest sequence length.https://blog.csdn.net/qq_15711195/article/details/122800843
本题为加强版：
LeetCode-126. Word Ladder IIhttps://leetcode.com/problems/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 si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.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.
Constraints:
1 <= beginWord.length <= 5endWord.length == beginWord.length1 <= wordList.length <= 1000wordList[i].length == beginWord.lengthbeginWord, endWord, and wordList[i] consist of lowercase English letters.beginWord != endWordAll the words in wordList are unique. 解题思路 【C++解法】 1. BFS：set + queue + vector
//这里再用map + vector就不合适了
unordered_map
for (string& w:wordList)
for(int i=0; i
....
mp.erase(key);
很明显dog log都和#og相关，erase会导致另一条路不能再走。
class Solution {
public:
vector> findLadders(string beginWord, string endWord, vector& wordList) {
vector< vector> res;
unordered_set dict(wordList.begin(),wordList.end());
if (dict.find(endWord) == dict.end()) {return res;}
queue> q;
q.push({beginWord});
bool flag = false;
while (!q.empty()){
int size = q.size();
while (size--){
vector curPath = q.front(); q.pop();
string last = curPath.back();
if (last == endWord) {
res.push_back(curPath);
flag = true;
continue;
}
dict.erase(last);
for (int i=0; i
【Java解法】
1. BFS：Set + Queue + List
class Solution {
public List> findLadders(String beginWord, String endWord, List wordList) {
List> res = new ArrayList<>();
Set dict = new linkedHashSet<>(wordList);
if (!dict.contains(endWord)) {return res;}
Queue> q = new linkedList<>();
q.offer(new ArrayList<>(Arrays.asList(beginWord)));
boolean flag = false;
while (!q.isEmpty()){
int size = q.size();
while (size-- > 0){
List curPath = q.poll();
String last = curPath.get(curPath.size()-1);
if (last.equals(endWord)) {
res.add(curPath);
flag = true;
continue;
}
dict.remove(last);
for (int i=0; i(curPath));
curPath.remove(curPath.size()-1);
}
}
}
}
if (flag) {break;}
}
return res;
}
}
2. Graph + BFS + DFS(reverse)
This solution search from endWord to beginWord, firstly do bfs to get shortest path and store distance and neighbor words infomation, secondly do dfs to get the paths:
1.Use a HashMap to record the distance between every word in wordlist and the beginWord during bfs.
2.Use a HashMap to record the the neighbor words list of the word(direction: from endWord to beginWord) during bfs.
3.Do dfs to add the words on the path and generate the answer.
class Solution {
public List> findLadders(String beginWord, String endWord, List wordList) {
Set dict = new HashSet<>(wordList);
List> ans = new ArrayList<>();
if (!dict.contains(endWord)) {return ans;}
Map> graph = new HashMap<>();
Map dist = new HashMap<>();
buildGraphByBFS(beginWord, graph, dist, dict);
dfs(endWord, beginWord, graph, dist, new ArrayList<>(), ans);
return ans;
}
public void buildGraphByBFS(String beginWord, Map> graph,
Map dist, Set dict) {
Queue queue = new linkedList<>();
queue.offer(beginWord);
dist.put(beginWord, 0);
for (String word : dict) {graph.put(word, new ArrayList<>());}
while (!queue.isEmpty()) {
String cur = queue.poll();
List neighbors = neighbors(cur, dict);
for (String next : neighbors) {
graph.get(next).add(cur);
if (!dist.containsKey(next)) {
dist.put(next, dist.get(cur) + 1);
queue.offer(next);
}
}
}
}
public void dfs(String curWord, String beginWord, Map> graph,
Map dist, List path, List> ans) {
path.add(curWord);
if (curWord.equals(beginWord)) {
Collections.reverse(path);
ans.add(new ArrayList<>(path));
Collections.reverse(path);
} else {
for (String next : graph.get(curWord)) {
if (dist.containsKey(next) && dist.get(curWord) == dist.get(next) + 1) {
dfs(next, beginWord, graph, dist, path, ans);
}
}
}
path.remove(path.size() - 1);
}
public List neighbors(String word, Set dict) {
List ans = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
char[] sc = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
sc[i] = c;
String temp = new String(sc);
if (dict.contains(temp)) {ans.add(temp);}
}
}
return ans;
}
}
3. Graph + BFS + DFS
do not reverse
class Solution {
public List> findLadders(String beginWord, String endWord, List wordList) {
List> res = new ArrayList<>(); // to store result
Map> graph = new HashMap<>(); // key -> word, value -> List of neighbors of 'word'
Set dict = new HashSet<>(wordList);
buildGraph(beginWord, endWord, dict, graph); // BFS step tp form the graph
shortestPath(beginWord, endWord, graph, res, new ArrayList<>()); // DFS step to find res
return res;
}
// build graph - BFS
// TC : O(N * W*26 + N * (N-1))
private void buildGraph(String begin, String end, Set dict, Map> graph) {
Queue q = new linkedList<>();
Set visited = new HashSet<>();
Set toBeVisited = new HashSet<>();
boolean foundEnd = false;
q.add(begin);
toBeVisited.add(begin);
while(!q.isEmpty()) {
visited.addAll(toBeVisited);
toBeVisited.clear();
int sz = q.size();
while (sz-- > 0) { // TC : O(N)
String currWord = q.poll();
for(String neighbor : getNeighbor(currWord, dict)) { // TC : O(N - 1)
if(end.equals(neighbor)) {foundEnd = true;}
if(!visited.contains(neighbor)) { // if neighbor has not been visited yet
graph.putIfAbsent(currWord, new ArrayList<>());
graph.get(currWord).add(neighbor);
}
if(!visited.contains(neighbor) && !toBeVisited.contains(neighbor)) {
q.add(neighbor);
toBeVisited.add(neighbor);
}
}
}
if(foundEnd) {break;}
}
}
// find the shortest path to endWord - DFS
// TC : O(N) -> N = wordList.length
// SC : O(N) -> recursion stack
private void shortestPath(String currWord, String endWord,
Map> graph, List> res, ArrayList temp) {
temp.add(currWord);
if(currWord.equals(endWord)) {res.add(new ArrayList<>(temp));}
else if (graph.containsKey(currWord)) {
for(String neighbor : graph.get(currWord))
shortestPath(neighbor, endWord, graph, res, temp);
}
temp.remove(temp.size() - 1);
}
// TC : O(W * 26)
// SC : O(W) -> W = word.length
private List getNeighbor(String word, Set dict) {
List res = new ArrayList<>();
for(int i = 0; i < word.length(); i++) {
char[] temp = word.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++) {
temp[i] = ch;
String newWord = String.valueOf(temp);
if(dict.contains(newWord)) {res.add(newWord);}
}
}
return res;
}
}
参考文献
【1】【Java】Java双端队列Deque使用详解_devnn的专栏-CSDN博客_deque java
【2】Java HashSet remove（）方法与示例_cumubi7453的博客-CSDN博客
【3】Java List初始化7种方式_旭东怪的博客-CSDN博客
【4】List、Set、Map的区别_weixin_30571465的博客-CSDN博客
【5】Java--集合大全List，Set，Map超详细讲解_Kevin.wang-CSDN博客_list、map、set
