LeetCode第 127 题：单词接龙(C++)_leetcode 127

127. 单词接龙 - 力扣（LeetCode）

要找最短的，直接bfs，bfs找到的肯定是最短的。

抽象在一个无向无权图中，每个单词作为节点，差距只有一个字母的两个单词之间连一条边。问题变成找到从起点到终点的最短路径，如果存在的话。因此可以使用广度优先搜索方法。

相当于每条边权值均为1的有向图，如果起始单词改变一个字母可以变为另一个单词，那么这两个单词之间的距离为1，否则为无穷。

怎么确定一个单词改变一个字母是不是能成为另一个单词呢？可以遍历两个单词进行统计，但是如果单词表太大的话，速度会很慢。

由于只有小写字母，可以使用遍历字母的方法，一次性检查所有的单词。

其实就是Dijkstra算法的变体，但是思路是一致的，每个单词即为顶点，如果两顶点之间可达，那么他们的距离为1（只用改变一个字母），那其实就转化为单点源路径问题了，只不过处理方式略有差别。

//Dijkstra算法的思路
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> set(wordList.begin(), wordList.end());
        if(!set.count(endWord)) return 0;
        queue<pair<string, int>> q;//<字符串，该字符串到beginword的距离>
        q.push({beginWord, 1});
        while(!q.empty()){
            string cur = q.front().first;
            int step = q.front().second;
            q.pop();
            if(cur == endWord)  return step;

            for(int i = 0; i < cur.size(); ++i){
                char ch = cur[i];
                //遍历字母来寻找距离为1（只用改变一个字母）的单词，也即可达的单词
                for(char c = 'a'; c <= 'z'; ++c){
                    if(c == ch) continue;
                    cur[i] = c;//替换单个字符
                    if(set.count(cur)){
                        q.push({cur, 1+step});
                        set.erase(cur);//该节点使用过了，需要进行删除
                    }
                }
                cur[i] = ch; //复原
            }
        }
        return 0;
    }
};
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
29
30
31

其中查找的部分，其实还可以使用字典树实现。