题目链接：127. 单词接龙

题解：

是上一道题的简化版，只需要记录方案数即可！

题目简述：

和上一题一样，给定起始和终止单词和一个字典，求每次只能改变一个单词并且该单词存在于字典可以到达终止单词的方案数！

题解：

具体见上一题： 可以通过博客上方搜索功能搜索或者使用文章下方上一篇按钮跳转！

由于只需要记录方案数，所以我们只需要上一道题的最短路的过程即可，即只需要BFS并在中途计数既可！

最终答案：if(t == endWord) return dist[t];

时间复杂度：同样见上一题分析，为O(26nL^2 + nL)即O(nL^2)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> S;
        unordered_map<string, int> dist;
        queue<string> q;
        q.push(beginWord);
        dist[beginWord] = 1;
        for(auto x : wordList) S.insert(x); 
        while(q.size()){
            auto s = q.front();
            q.pop();
            for(int i = 0; i < s.size(); i++){
                string t = s;
                for(char j = 'a'; j <= 'z'; j++){
                    if(j == s[i]) continue;
                    t[i] = j;
                    if(S.count(t) && dist.count(t) == 0){
                        dist[t] = dist[s] + 1;
                        if(t == endWord) return dist[t];
                        q.push(t);
                    }
                }
            }
        }
        return 0;
    }
};