单词接龙 II 图解题解

这道题到底在问什么

beginWord

"hit"

endWord

"cog"

wordList

[hot,dot,dog,lot,log,cog]

输出

[[hit,hot,dot,dog,cog],[hit,hot,lot,log,cog]]

最优解：一步一步想明白

1. 3换个眼光:单词是地图上的点,差一个字母的两词之间有路。问题变成了我们熟悉的图上最短路。
2. 4光找到最短长度不够,还要能还原路径。诀窍:BFS 分层时给每个新词记下它的全部前驱(上一层谁能一步变到它)。
3. 5下面一帧一帧演:先看 BFS 怎么逐层扩散并记前驱,再看怎么沿前驱回溯拼出全部路径。
4. 6queue=[hit],已访问={hit}起跑线:把 hit 入队,记它在第 0 层、已访问。灰边是「差一个字母」的潜在连接,后面 BFS 会逐条点亮真正走通的边。
5. 7hit 的邻居 = hot扩展 hit:词表里只有 hot 和它差一个字母(hit→hot)。hot 进入第 1 层,记 parents[hot]={hit}。
6. 8parents[hot]={hit}第 0 层处理完(hit 变绿表示已确定)。第 1 层只有 hot,它的前驱已记为 {hit}。这层没有 cog,继续往外扩第 2 层。
7. 9hot 邻居 = dot, lot扩展 hot:改首字母能得到 dot(h→d)和 lot(h→l),都在词表。两条岔路同时打开——这正是后面会有两条最短路的根源。记 parents[dot]={hot}、parents[lot]={hot}。
8. 10parents[dot]={hot}, parents[lot]={hot}hot 处理完变绿。第 2 层有 dot、lot 两个词,各自记好前驱。仍没碰到 cog,继续扩第 3 层。注意 BFS 同层一起推进,不偏不倚。
9. 11dot 邻居 = dog(hot 已访问跳过)扩展 dot:改尾字母得 dog(dog)。hot 已访问、跳过。dog 进第 3 层,记 parents[dog]={dot}。
10. 12lot 邻居 = log扩展 lot:改尾字母得 log(log)。log 进第 3 层,记 parents[log]={lot}。两条岔路平行向前,都还没到终点。
11. 13parents[dog]={dot}, parents[log]={lot}第 2 层全处理完(dot、lot 变绿)。第 3 层有 dog、log。它们到 cog 各差一个字母,下一层很可能命中——但纪律上仍要把这一层扩完。
12. 14dog → cog(d→c)扩展 dog:改首字母得 cog(cog)——终点!cog 进第 4 层,记 parents[cog]={dog}。但别急着停,本层还有 log 没扩。
13. 15log → cog,parents[cog] 再加 log扩展 log:也能一步到 cog(log→cog)。cog 已在第 4 层,所以不重复入队,只把 log 追加进 parents[cog]。现在 parents[cog]={dog, log}——两条边都通向终点。
14. 16最短长度 4 锁定,parents 记账完毕第 4 层处理完,cog 在本层出现,最短长度锁定为 4 次变换。整张前驱图也建好了:parents 记下了每个词的所有上层来源。下面进入第二阶段——沿前驱回溯拼出所有路径。
15. 17path = [cog]回溯从终点 cog 起,倒着往回拼。看前驱表:parents[cog]={dog, log}——有两个来源,意味着待会儿会分裂成两条路。
16. 18path = [dog, cog]先走第一条分支:cog 的前驱取 dog,接到路径头部 → [dog, cog]。再查 parents[dog]={dot},只有一个来源,继续往回。
17. 19path = [dot, dog, cog]继续:dog 的前驱是 dot → [dot, dog, cog]。查 parents[dot]={hot},再往回接 hot。路径一格格朝起点生长。
18. 20path = [hot, dot, dog, cog]dot 的前驱是 hot → [hot, dot, dog, cog]。查 parents[hot]={hit},而 hit 就是起点——再接一步就到头了。
19. 21path = [hit, hot, dot, dog, cog]接上起点 hit,触到 beginWord,第一条最短路完工:hit→hot→dot→dog→cog。现在回到 cog 那个分叉口,走另一条分支 log。
20. 22path = [log, cog]回到 cog 的分叉口,这次取另一个前驱 log → [log, cog]。查 parents[log]={lot},继续往回拼。
21. 23path = [lot, log, cog]log 的前驱是 lot → [lot, log, cog]。查 parents[lot]={hot},殊途同归——又回到了 hot。
22. 24path = [hot, lot, log, cog]lot 的前驱是 hot → [hot, lot, log, cog]。再查 parents[hot]={hit},下一步接上起点就收尾。
23. 25path = [hit, hot, lot, log, cog]接上 hit,第二条最短路也完工:hit→hot→lot→log→cog。两个分支都回到起点,回溯结束。
24. 26两条等长(4 步)最短路整张图看:从 hit 到 cog 共有 两条等长(4 步)的最短路,在 hot 处分叉、在 cog 处汇合。BFS 记前驱 + 回溯,把它们一条不漏地还原了出来。
25. 30cog 同时被 dog、log 指向放大看终点 cog:dog 和 log 都能一步变到它。若 parents 只记一个父亲,回溯就只能拼出一条路,另一条凭空消失。所以前驱必须用集合/列表存全部来源。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import deque, defaultdict
def findLadders(beginWord, endWord, wordList):
    words = set(wordList)
    if endWord not in words: return []
    parents = defaultdict(set)
    visited = {beginWord}
    level = {beginWord}
    found = False
    while level and not found:
        nxt = set()
        for w in level:
            for i in range(len(w)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    t = w[:i] + c + w[i+1:]
                    if t in words and t not in visited:
                        if t == endWord: found = True
                        nxt.add(t)
                        parents[t].add(w)
        visited |= nxt
        level = nxt
    if not found: return []
    res, paths = [], [[endWord]]
    while paths and paths[0][0] != beginWord:
        np = []
        for p in paths:
            for pre in parents[p[0]]:
                np.append([pre] + p)
        paths = np
    return paths

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        vector<vector<string>> res;
        if (!words.count(endWord)) return res;
        unordered_map<string, vector<string>> parents;
        unordered_set<string> visited{beginWord};
        unordered_set<string> level{beginWord};
        bool found = false;
        while (!level.empty() && !found) {
            unordered_set<string> nxt;
            for (string w : level) {
                for (int i = 0; i < (int)w.size(); ++i) {
                    char old = w[i];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        w[i] = c;
                        if (words.count(w) && !visited.count(w)) {
                            if (w == endWord) found = true;
                            nxt.insert(w);
                            parents[w].push_back(w.substr(0,i)+old+w.substr(i+1));
                        }
                    }
                    w[i] = old;
                }
            }
            for (const string& s : nxt) visited.insert(s);
            level = nxt;
        }
        if (!found) return res;
        vector<vector<string>> paths{{endWord}};
        while (!paths.empty() && paths[0][0] != beginWord) {
            vector<vector<string>> np;
            for (auto& p : paths)
                for (string& pre : parents[p[0]]) {
                    vector<string> q{pre};
                    q.insert(q.end(), p.begin(), p.end());
                    np.push_back(q);
                }
            paths = np;
        }
        return paths;
    }
};

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!words.contains(endWord)) return res;
        Map<String, List<String>> parents = new HashMap<>();
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Set<String> level = new HashSet<>();
        level.add(beginWord);
        boolean found = false;
        while (!level.isEmpty() && !found) {
            Set<String> nxt = new HashSet<>();
            for (String w : level) {
                char[] arr = w.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    char old = arr[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        arr[i] = c;
                        String t = new String(arr);
                        if (words.contains(t) && !visited.contains(t)) {
                            if (t.equals(endWord)) found = true;
                            nxt.add(t);
                            parents.computeIfAbsent(t, k -> new ArrayList<>()).add(w);
                        }
                    }
                    arr[i] = old;
                }
            }
            visited.addAll(nxt);
            level = nxt;
        }
        if (!found) return res;
        List<List<String>> paths = new ArrayList<>();
        List<String> init = new ArrayList<>(); init.add(endWord);
        paths.add(init);
        while (!paths.isEmpty() && !paths.get(0).get(0).equals(beginWord)) {
            List<List<String>> np = new ArrayList<>();
            for (List<String> p : paths)
                for (String pre : parents.getOrDefault(p.get(0), new ArrayList<>())) {
                    List<String> q = new ArrayList<>(); q.add(pre); q.addAll(p);
                    np.add(q);
                }
            paths = np;
        }
        return paths;
    }
}

复杂度

面试官可能追问