单词接龙 图解题解

这道题到底在问什么

输入

begin="hit", end="cog"

输出

5

最优解：一步一步想明白

1. 3记住：每条边只差一个字母，BFS 逐层保证第一次到达就是最短。
2. 4先把 10 个词全摆上：节点=单词，两词相差一个字母就连边。还没开始搜，全是灰的。
3. 5起点 hit 入队，dist=1（它是序列第 1 个词）。队列：[hit]。
4. 6出队 hit（标记为正在访问），看它能一步变成哪些还没访问过的词。
5. 7hit 改一个字母可得 hot（走这条边），它的 dist = hit 的层 +1 = ②，入队。队列：[hot]。
6. 8hit 改一个字母可得 hut（走这条边），它的 dist = hit 的层 +1 = ②，入队。队列：[hot, hut]。
7. 9hit 改一个字母可得 lit（走这条边），它的 dist = hit 的层 +1 = ②，入队。队列：[hot, hut, lit]。
8. 10出队 hot（标记为正在访问），看它能一步变成哪些还没访问过的词。
9. 11hot 改一个字母可得 dot（走这条边），它的 dist = hot 的层 +1 = ③，入队。队列：[hut, lit, dot]。
10. 12hot 改一个字母可得 lot（走这条边），它的 dist = hot 的层 +1 = ③，入队。队列：[hut, lit, dot, lot]。
11. 13hot 改一个字母可得 bot（走这条边），它的 dist = hot 的层 +1 = ③，入队。队列：[hut, lit, dot, lot, bot]。
12. 14出队 hut（标记为正在访问），看它能一步变成哪些还没访问过的词。
13. 15出队 lit（标记为正在访问），看它能一步变成哪些还没访问过的词。
14. 16出队 dot（标记为正在访问），看它能一步变成哪些还没访问过的词。
15. 17dot 改一个字母可得 dog（走这条边），它的 dist = dot 的层 +1 = ④，入队。队列：[lot, bot, dog]。
16. 18出队 lot（标记为正在访问），看它能一步变成哪些还没访问过的词。
17. 19lot 改一个字母可得 log（走这条边），它的 dist = lot 的层 +1 = ④，入队。队列：[bot, dog, log]。
18. 20出队 bot（标记为正在访问），看它能一步变成哪些还没访问过的词。
19. 21bot 改一个字母可得 bog（走这条边），它的 dist = bot 的层 +1 = ④，入队。队列：[dog, log, bog]。
20. 22出队 dog（标记为正在访问），看它能一步变成哪些还没访问过的词。
21. 23dog 改一个字母可得 cog（走这条边），它的 dist = dog 的层 +1 = ⑤，入队。队列：[log, bog, cog]。
22. 24出队 log（标记为正在访问），看它能一步变成哪些还没访问过的词。
23. 25出队 bog（标记为正在访问），看它能一步变成哪些还没访问过的词。
24. 26出队 cog —— 正是终点！它的 dist=⑤，即最短序列共 5 个词。BFS 第一次到达就是最短，搜索结束。
25. 27最短转换链：hit → hot → dot → dog → cog，共 5 个词。每相邻两词只差一个字母（一条边），这就是 hit 变到 cog 的最少步数。

⚠️ 容易写错的地方

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

from collections import deque
def ladderLength(begin, end, wordList):
    ws = set(wordList)
    if end not in ws: return 0
    q = deque([(begin, 1)])
    seen = {begin}
    while q:
        w, d = q.popleft()
        if w == end: return d
        for i in range(len(w)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                nx = w[:i] + c + w[i+1:]
                if nx in ws and nx not in seen:
                    seen.add(nx); q.append((nx, d + 1))
    return 0

int ladderLength(string begin, string end, vector<string>& wl){
    unordered_set<string> ws(wl.begin(), wl.end());
    if(!ws.count(end)) return 0;
    queue<pair<string,int>> q; q.push({begin,1});
    unordered_set<string> seen{begin};
    while(!q.empty()){
        auto [w,d]=q.front(); q.pop();
        if(w==end) return d;
        for(int i=0;i<(int)w.size();i++){
            string nx=w;
            for(char c='a';c<='z';c++){ nx[i]=c;
                if(ws.count(nx)&&!seen.count(nx)){ seen.insert(nx); q.push({nx,d+1}); } }
        }
    }
    return 0;
}

public int ladderLength(String begin, String end, List<String> wl){
    Set<String> ws = new HashSet<>(wl);
    if(!ws.contains(end)) return 0;
    Queue<String> q = new LinkedList<>(); q.add(begin);
    Set<String> seen = new HashSet<>(); seen.add(begin);
    int d = 1;
    while(!q.isEmpty()){
        int sz = q.size();
        for(int k=0;k<sz;k++){
            String w = q.poll();
            if(w.equals(end)) return d;
            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 nx = new String(arr);
                    if(ws.contains(nx)&&!seen.contains(nx)){ seen.add(nx); q.add(nx); } }
                arr[i]=old;
            }
        }
        d++;
    }
    return 0;
}

复杂度

面试官可能追问