一、题目描述
二、算法原理
思路：跟边权为 1 的最短路径一样，使用 BFS 算法就能解决
https://blog.csdn.net/2403_84958571/article/details/157183596?spm=1011.2415.3001.10575&sharefrom=mp_manage_link
三、代码实现
class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> hash_w(wordList.begin(),wordList.end());//单词库 unordered_set<string> hash_b; hash_b.insert(beginWord);//防止遍历过 queue<string> que;//使用队列实现 BFS que.push(beginWord); int count = 1;//记录最短实现的步骤 while(que.size()) { int qor = que.size(); count++;//每层都会有个变化的单词 while(qor--) { string tmp = que.front(); que.pop(); for(int i = 0; i < tmp.size(); i++) { for(char k = 'a'; k <= 'z'; k++)//枚举各种可能 { string tmp_str = tmp; tmp_str[i] = k; if(!hash_b.count(tmp_str) && hash_w.count(tmp_str))//让下一个层进入 { que.push(tmp_str); hash_b.insert(tmp_str); if(tmp_str == endWord) return count; } } } } } //无法演化到 endword return 0; } };
