单词接龙 图解题解

这道题到底在问什么

begin/end

hit → cog

输出

5

最优解：一步一步想明白

1. 3关键不是背模板，而是看懂为什么这题适合图 · BFS。
2. 4BFS 从 hit 出发，距离记 1。每次把当前单词「改一位字母」，若新词在词表里就是它的邻居。
3. 5h_t→hot、_it/hi_ 都不在词表，只有 hot 命中 → hot 是 hit 的邻居。
4. 6hot 入队、距离 2。BFS 逐层扩展，第一次到某词时的距离一定最短。
5. 7hot 改一位得 dot、lot(都在词表)→ 同一层一起入队，距离 3。
6. 8dot→dog、lot→log，第 4 层入队，距离 4。
7. 9dog 和 log 各改一位都能到 cog → cog 距离 5。
8. 10BFS 按层推进、距离从小到大，第一次碰到 cog 的距离 5 就是答案(最短变换序列的单词数)。
9. 11BFS 是一圈圈向外扩：先访问距离 1 的、再距离 2…… 同一距离的节点一起处理。所以任何节点「第一次被访问」时的距离必然是它的最短距离，无需再更新。
10. 14把这句话记住，下次遇到同类题，就能更快选出方向。

⚠️ 容易写错的地方

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

from collections import deque
class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        words = set(wordList)
        if endWord not in words: return 0
        q = deque([(beginWord, 1)])
        seen = {beginWord}
        while q:
            word, dist = q.popleft()
            if word == endWord: return dist
            for i in range(len(word)):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    nxt = word[:i] + c + word[i+1:]   # 改第 i 位
                    if nxt in words and nxt not in seen:
                        seen.add(nxt)
                        q.append((nxt, dist + 1))
        return 0

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> words(wordList.begin(), wordList.end());
        if (!words.count(endWord)) return 0;
        queue<pair<string,int>> q; q.push({beginWord, 1});
        unordered_set<string> seen{beginWord};
        while (!q.empty()) {
            auto [word, dist] = q.front(); q.pop();
            if (word == endWord) return dist;
            for (int i = 0; i < (int)word.size(); i++) {
                string nxt = word;
                for (char c = 'a'; c <= 'z'; c++) {
                    nxt[i] = c;
                    if (words.count(nxt) && !seen.count(nxt)) {
                        seen.insert(nxt); q.push({nxt, dist + 1});
                    }
                }
            }
        }
        return 0;
    }
};

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<>(wordList);
        if (!words.contains(endWord)) return 0;
        Queue<String> q = new LinkedList<>(); q.offer(beginWord);
        Set<String> seen = new HashSet<>(); seen.add(beginWord);
        int dist = 1;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz > 0; sz--) {
                String word = q.poll();
                if (word.equals(endWord)) return dist;
                char[] a = word.toCharArray();
                for (int i = 0; i < a.length; i++) {
                    char old = a[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        a[i] = c; String nxt = new String(a);
                        if (words.contains(nxt) && !seen.contains(nxt)) {
                            seen.add(nxt); q.offer(nxt);
                        }
                    }
                    a[i] = old;
                }
            }
            dist++;
        }
        return 0;
    }
}

# 图 · BFS 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界

复杂度

面试官可能追问