给定一个起始字符串和一个终止字符串，以及一个单词表，求是否可以将起始字符串每次改一个字符，直到改成终止字符串，且所有中间的修改过程表示的字符串都可以在单词表里找到。若存在，输出需要修改次数最少的所有更改方式。
输入是两个字符串，输出是一个二维字符串数组，表示每种字符串修改方式。
示例：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"
可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成结点。若两个字符串只有一个字符不同，那么它们相连。因为题目需要输出修改次数最少的所有修改方式，看到“最短”、“最少”就想到 BFS，求得起始结点到终止结点的最短距离。
（可以用DFS，但是时间过长，具体可以看这篇Java题解 详细通俗的思路分析，多解法）
如果两个单词可以只改变一个字母进行转换，那么说明两个结点之间有一条双向边（原因：如果可以从一个单词 word1 转换成为单词 word2，那么一定可以从单词 word2 转换成为 word1）。因此只需要把满足转换条件的点相连，就形成了一张无向图。
这样就是以 “hit" 为图的起点， 以 “cog" 为终点进行广度优先搜索，寻找 “hit" 到 “cog" 的最短路径。
由于要求输出所有的最短路径，因此需要记录遍历路径，然后通过回溯得到所有的最短路径。由于要找“最短”，如果位于广度优先遍历同一层的单词之间有边连接，不可以被记录下来。
但是同时要记录路径，因此需要一个哈希表记录遍历到的单词在第几层。
综上，在广度优先遍历的时候需要记录：从当前的单词 currWord 只变化了一个字符以后，且又在单词字典中的单词 nextWord 之间的单向关系（虽然实际上无向图，但是广度优先遍历是有方向的，解决这个问题可以只看成有向图），记为 from，它是一个映射关系：键是单词，值是广度优先遍历的时候从哪些单词可以遍历到「键」所表示的单词，使用哈希表来保存。
双层BFS
可以使用一个小技巧：不直接从起始结点进行广度优先搜索，直到找到终止结点为止；而是从起始结点和终止结点分别进行广度优先搜索，每次只延展当前层结点数最少的那一端，这样就可以减少搜索的总结点数。
举例：假设最短距离为 4，如果只从一端搜索 4 层，总遍历结点数最多是 1 + 2 + 4 + 8 + 16 = 31；而如果从两端各搜索两层，总遍历结点数最多只有 2 × (1 + 2 + 4) = 14
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
if endWord not in wordList:
return []
qu = collections.deque([(beginWord, [[beginWord]])])
while qu:
s = len(qu)
qui = {}
for i in range(s):
a = qu.popleft()
if a[0] == endWord:
return a[1]
f = set()
for wi in range(len(wordList)):
if wordList[wi] == '0':
continue
sa = 0
for j in range(len(a[0])):
if a[0][j] != wordList[wi][j]:
sa += 1
if sa > 1:
break
if sa == 1:
if wordList[wi] not in qui:
qui[wordList[wi]] = [ai + [wordList[wi]] for ai in a[1]]
else:
qui[wordList[wi]] = qui[wordList[wi]] + [ai + [wordList[wi]] for ai in a[1]]
f.add(wi)
for quik in qui:
qu.append((quik, qui[quik]))
wordList[wordList.index(quik)] = '0'
return []
超时。
BFS + DFS回溯
广度优先遍历建图 + 深度优先遍历找到所有解（Java）
坐等大佬再更新双层BFS
@Java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
// 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
Set<String> dict = new HashSet<>(wordList);
// 特殊用例判断
if (!dict.contains(endWord)) {
return res;
}
// 因为从 beginWord 开始扩展，因此 dict 里一定不可以有 beginWord
dict.remove(beginWord);
// 第 1 步：广度优先遍历构建图
// 为了避免记录不需要的边，我们需要记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层
// steps 记录了已经访问过的 word 集合，同时记录了在第几层访问到
Map<String, Integer> steps = new HashMap<>();
steps.put(beginWord, 0);
// 记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系，dfs 的时候会用到
Map<String, Set<String>> from = new HashMap<>();
boolean found = bfs(beginWord, endWord, dict, steps, from);
// 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
if (found) {
Deque<String> path = new ArrayDeque<>();
path.add(endWord);
dfs(from, path, beginWord, endWord, res);
}
return res;
}
private boolean bfs(String beginWord, String endWord, Set<String> dict, Map<String, Integer> steps, Map<String, Set<String>> from) {
int wordLen = beginWord.length();
int step = 0;
boolean found = false;
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
while (!queue.isEmpty()) {
step++;
int size = queue.size();
for (int i = 0; i < size; i++) {
String currWord = queue.poll();
char[] charArray = currWord.toCharArray();
for (int j = 0; j < wordLen; j++) {
char origin = charArray[j];
for (char c = 'a'; c <= 'z'; c++) {
// 将每一位替换成 26 个小写英文字母
charArray[j] = c;
String nextWord = String.valueOf(charArray);
// 注意：这几行代码的逻辑先后顺序
if (steps.containsKey(nextWord) && steps.get(nextWord) == step) {
from.get(nextWord).add(currWord);
}
if (!dict.contains(nextWord)) {
continue;
}
dict.remove(nextWord);
// dict 和 steps 承担了已经访问的功能
queue.offer(nextWord);
// 维护 from、steps、found 的定义
from.putIfAbsent(nextWord, new HashSet<>());
from.get(nextWord).add(currWord);
steps.put(nextWord, step);
if (nextWord.equals(endWord)) {
// 注意：由于有多条路径到达 endWord 找到以后不能立即退出，只需要设置 found = true 即可
found = true;
}
}
charArray[j] = origin;
}
}
if (found) {
break;
}
}
return found;
}
private void dfs(Map<String, Set<String>> from, Deque<String> path, String beginWord, String cur, List<List<String>> res) {
if (cur.equals(beginWord)) {
res.add(new ArrayList<>(path));
return;
}
for (String precursor : from.get(cur)) {
path.addFirst(precursor);
dfs(from, path, beginWord, precursor, res);
path.removeFirst();
}
}
}
作者：liweiwei1419
链接：https://leetcode.cn/problems/word-ladder-ii/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you--2/
Dijkstra求最短路径 + DFS重建单词转换路径（C++）
bfs 就是边的权重都为 1 时的 Dijkstra
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord,
vector<string> &wordList) {
vector<vector<string>> ret;
auto it = find(wordList.begin(),wordList.end(), endWord);
if (it == wordList.end())
return ret;
int src, dst;
dst = it - wordList.begin();
it = find(wordList.begin(),wordList.end(), beginWord);
if (it == wordList.end()) {
wordList.push_back(beginWord);
src = wordList.size() - 1;
} else {
src = it - wordList.begin();
}
int wordLen = beginWord.size();
// 构建邻接表
vector<vector<int>> graph(wordList.size());
for (int i = 0; i < wordList.size(); i++) {
for (int j = i + 1; j < wordList.size(); j++) {
int cnt = 0;
for (int k = 0; k < wordLen; ++k) {
if (wordList[i][k] != wordList[j][k])
cnt++;
if (cnt > 1)
break;
}
作者：destinygang-UtZgjuB0v8
链接：https://leetcode.cn/problems/word-ladder-ii/solution/by-destinygang-utzgjub0v8-2tdu/