数据结构算法--单词接龙(C++)

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

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

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

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

由于只有小写字母，可以使用遍历字母的方法，一次性检查所有的单词，具体减代码;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string>  s(wordList.begin(), wordList.end());

        queue<pair<string, int>> q;
        q.push({beginWord, 1});//第一个元素是字符串，第二个是该字符串到beginword的序列长度

        while(!q.empty()){
            string tmp = q.front().first;
            int step = q.front().second;
            q.pop();
            if(tmp == endWord)  return step;//走到了终点

            for(int i = 0; i < tmp.size(); ++i){
                char ch = tmp[i];
                //遍历字母来寻找距离为1（只用改变一个字母）的单词
                for(char c = 'a'; c <= 'z'; ++c){
                    if(ch == c) continue;
                    tmp[i] = c;//替换单个字符
                    if(s.count(tmp)){
                        q.push({tmp, 1+step});
                        s.erase(tmp);//该节点使用过了，可以删除
                    }
                }
                tmp[i] = ch;//复原
            }
        }
        return 0;
    }
}; 

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

本文地址：https://blog.csdn.net/qq_32523711/article/details/108239342