leetCode127. 单词接龙

leetCode127. 单词接龙

// bfs + 剪枝
class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {// 1.将所有的单词放在set字段中unordered_set<string> s;for (auto & ele : wordList) s.insert(ele);// 单词 + 步数queue<pair<string,int> > que;que.push({beginWord,1});s.erase(biginWord);// 避免再次找到次字符串，避免找回来int step = 0;string temp = "";while (!que.empty()) {if (que.front().first == endWord) {return que.front().second;}temp = que.front().first;step = que.front().second;que.pop();// bfs下一个结点，就是将beginWord挨个替换char ch;for (int i = 0; i < temp.size(); ++ i) {ch = temp[i];for (char j = 'a'; j <= 'z'; ++ j ) {if (j == ch) continue; // 已存在的不进行寻找temp[i] = j;// 如果在字典中if (s.find(temp) != s.end()) {que.push({temp,step + 1});// 同时让其字典伤处这个元素，避免查找回来s.erase(temp);}}// 复原 = 回溯temp[i] = ch;}}return 0;}
};