leetcode 127 C++
题目描述
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]输出: 5解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",返回它的长度 5。示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]输出: 0解释: endWord "cog" 不在字典中，所以无法进行转换。解法一：BFS
算法
-
对给定的 wordList 做预处理，找出所有的通用状态。将通用状态记录在字典中，键是通用状态，值是所有具有通用状态的单词。
-
将包含 beginWord 和 1 的元组放入队列中，1 代表节点的层次。我们需要返回 endWord 的层次也就是从 beginWord 出发的最短距离。
-
为了防止出现环，使用访问数组记录。
-
当队列中有元素的时候，取出第一个元素，记为 current_word。
-
找到 current_word 的所有通用状态，并检查这些通用状态是否存在其它单词的映射，这一步通过检查 all_combo_dict 来实现。
-
从 all_combo_dict 获得的所有单词，都和 current_word 共有一个通用状态，所以都和 current_word 相连，因此将他们加入到队列中。
-
对于新获得的所有单词，向队列中加入元素 (word, level + 1) 其中 level 是 current_word 的层次。
-
最终当你到达期望的单词，对应的层次就是最短变换序列的长度。
标准广度优先搜索的终止条件就是找到结束单词。
链接：https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode/
class Solution {
public:int ladderLength(string beginWord, string endWord, vector& wordList) {unordered_map> allComboDict;int L = beginWord.size();for(auto item : wordList){for(int i = 0;i < L;i++){string newWord = item.substr(0, i) + '*' + item.substr(i+1, L);vector trans;if(allComboDict.find(newWord) == allComboDict.end()){allComboDict.insert(pair>(newWord, trans));allComboDict[newWord].push_back(item);}else{allComboDict[newWord].push_back(item);}}}//queue for BFSqueue> newQueue;//pair usagenewQueue.push(pair(beginWord, 1));//visited Hashmapunordered_map visited;visited.insert(pair(beginWord, true));while(!newQueue.empty()){pair node = newQueue.front();newQueue.pop();int level = node.second;for(int i = 0;i < L;i++){string newWord = node.first.substr(0, i) + '*' + node.first.substr(i+1, L);for(auto adjacentWord : allComboDict[newWord]){if(adjacentWord == endWord){return level + 1;}if(visited.find(adjacentWord) == visited.end()){visited.insert(pair(adjacentWord, true));newQueue.push(pair(adjacentWord, level + 1));}}}}return 0;}};
解法二：双向BFS
算法
-
算法与之前描述的标准广搜方法相类似。
-
唯一的不同是我们从两个节点同时开始搜索，同时搜索的结束条件也有所变化。
-
我们现在有两个访问数组，分别记录从对应的起点是否已经访问了该节点。
-
如果我们发现一个节点被两个搜索同时访问，就结束搜索过程。因为我们找到了双向搜索的交点。过程如同从中间相遇而不是沿着搜索路径一直走。
双向搜索的结束条件是找到一个单词被两边搜索都访问过了。
-
最短变换序列的长度就是中间节点在两边的层次之和。因此，我们可以在访问数组中记录节点的层次。
链接：https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode/
class Solution {
public:int L = 0;unordered_map> allComboDict;int ladderLength(string beginWord, string endWord, vector& wordList) {if(count(wordList.begin(), wordList.end(), endWord) == 0)return 0;L = beginWord.size();for(auto item : wordList){for(int i = 0;i < L;i++){string newWord = item.substr(0, i) + '*' + item.substr(i+1, L);vector trans;if(allComboDict.find(newWord) == allComboDict.end()){allComboDict.insert(pair>(newWord, trans));allComboDict[newWord].push_back(item);}else{allComboDict[newWord].push_back(item);}}}//queue for BFSqueue> newQueue_begin;//pair usagenewQueue_begin.push(pair(beginWord, 1));queue> newQueue_end;//pair usagenewQueue_end.push(pair(endWord, 1));//visited Hashmapunordered_map visitedBegin;visitedBegin.insert(pair(beginWord, 1));unordered_map visitedEnd;visitedEnd.insert(pair(endWord, 1));while(!newQueue_begin.empty() && !newQueue_end.empty()){int ans = visitWordNode(newQueue_begin, visitedBegin, visitedEnd);if(ans > -1){return ans;}//cout< -1){return ans;}}return 0;}//三个&不可少int visitWordNode(queue>& Q, unordered_map& visited, unordered_map& othervisited){pair node = Q.front();Q.pop();int level = node.second;for(int i = 0;i < L;i++){string newWord = node.first.substr(0, i) + '*' + node.first.substr(i+1, L);for(auto adjacentWord : allComboDict[newWord]){/*if(adjacentWord == endWord){return level + 1;}*/if(othervisited.find(adjacentWord) != othervisited.end()){return level + othervisited[adjacentWord];}if(visited.find(adjacentWord) == visited.end()){visited.insert(pair(adjacentWord, level + 1));Q.push(pair(adjacentWord, level + 1));}}}return -1;}};
解法三：DFS
此方法会超时。
class Solution {
public:int sumRes = INT_MAX;int ladderLength(string beginWord, string endWord, vector& wordList) {if(count(wordList.begin(), wordList.end(), endWord) == 0 || beginWord.size() != endWord.size()){return 0;}ladderLengthCore(beginWord, endWord, wordList, 1);if(sumRes == INT_MAX)return 0;elsereturn sumRes;}void ladderLengthCore(string beginWord, string endWord, vector wordList, int cnt){if(beginWord == endWord){sumRes = min(cnt, sumRes);return;}for(int i = 0;i < wordList.size();i++){if(cntWordDiff(beginWord, wordList[i]) == 1){string tempString = wordList[i];wordList.erase(wordList.begin() + i, wordList.begin() + i + 1);ladderLengthCore(tempString, endWord, wordList, cnt+1);wordList.insert(wordList.begin() + i, tempString);}}return;}int cntWordDiff(string firstWord, string secondWord){int diffNum = 0;for(int i = 0;i < firstWord.size();i++){if(firstWord[i] != secondWord[i]){diffNum++;}}return diffNum;}};
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！