126. Word Ladder II 、 127. Word Ladder（leetcode BFS+DFS)

2019-11-08 03:08:48

字体：大中小

来源：转载

供稿：网友

127. Word Ladder 题目地址

https://leetcode.com/PRoblems/word-ladder/

ac

ac代码餐卡博主：陆草纯地址：http://www.cnblogs.com/ganganloveu/p/4125695.html 直接采用bfs, 注意判重，解map,set结构

struct Node{ string word; int len; Node(string w, int l): word(w), len(l) {}};class Solution {public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { int len1 = beginWord.size(); int len2 = endWord.size(); if(len1 != len2) return 0; unordered_set<string> wordDict; // 字典集合 vector<string>::iterator it = wordList.begin(); while(it != wordList.end()) { wordDict.insert(*it); ++it; } if(wordDict.find(endWord) == wordDict.end()) return 0; queue<Node*> que; unordered_map<string,bool> mp; // 记录是否访问到了 Node* beginNode = new Node(beginWord, 1); que.push(beginNode); mp[beginWord] = true; while(!que.empty()) { Node* frontNode = que.front(); que.pop(); string frontWord = frontNode->word; int len = frontWord.size(); // for(int i=0;i<len;i++) { for(char c = 'a'; c <= 'z'; c++) { if(c == frontWord[i]) continue; string frontWordTmp = frontWord; frontWordTmp[i] = c; //相邻的string if(frontWordTmp == endWord) return frontNode->len + 1; // 字典中有此相邻单词，并且没有被访问到 if(wordDict.find(frontWordTmp) != wordDict.end()) { if(mp[frontWordTmp] == false) { Node* tmp = new Node(frontWordTmp, frontNode->len + 1); mp[frontWordTmp] = true; que.push(tmp); } } } } // end for } // end while return 0; }};

126. Word Ladder II题目地址

https://leetcode.com/problems/word-ladder-ii/

ac

如果采用上面的思路，会出现错误一是每个string的前一个stirng可能有多个而是超时问题

本题的ac思路参考博主：会咬人的兔子地址：http://www.cnblogs.com/93scarlett/p/6376822.html

先用bfs构建出一个邻接表

具体是每一string,替换一个字母可以有哪些string

同时记录每一个字符能从开始字符到其的步骤数

最后采用dfs,对上诉构造出来的图进行遍历，求解

ac代码如如下通过Debug，next和step的运行后的情况这里写图片描述

class Solution {public: vector<vector<string> > ans; vector<string> path; vector<vector<string>> findLadders(string start, string end, vector<string> &wordList) { ans.clear(); unordered_set<string> dict; vector<string>::iterator it = wordList.begin(); while(it != wordList.end()) { dict.insert(*it); ++it; } if(dict.find(end) == dict.end()) return ans; int len = start.size(); // 字符串的长度 unordered_map<string, vector<string>> next; // 某个字符，经过一步变换，可以得到的所有字符串 unordered_map<string, int> step; // 某个字符串从start经过几步可以得到 queue<string> que; // 遍历所有字符使用的队列 que.push(start); step[start] = 0; while (!que.empty()) { string curstr = que.front(); que.pop(); if (curstr == end) break; int curstep = step[curstr]; vector<string> snext; for (int i = 0; i < len; i++) {//因为不需要记步数了所以不要了只用一个map来记录谁是第几步 string newstr = curstr; for (char c = 'a'; c <= 'z'; c++) { newstr[i] = c; if (c == curstr[i] || dict.find(newstr) == dict.end()) continue; auto it = step.find(newstr); if (it == step.end()) {//从来没visit过的虽然省略了q.size()的for循环,在这里也不会重复 que.push(newstr); step[newstr] = curstep + 1;//加一步 } snext.push_back(newstr); } } next[curstr] = snext; } path.push_back(start); dfspath(next, step, start, end); return ans; } void dfspath(unordered_map<string, vector<string> > &next, unordered_map<string, int> &step, string now, string end){ if (now == end){ ans.push_back(path); //寻到了一条路径，把路径加入结果 } else { vector<string> nextStrs = next[now]; int stepNow = step[now]; for (int i = 0; i < (int)nextStrs.size(); i++) { //对于每一个可能的next step进行遍历 if (step[nextStrs[i]] != stepNow + 1) continue; path.push_back(nextStrs[i]); dfspath(next, step, nextStrs[i], end); path.pop_back(); } } }};

上一篇：SteamVR+HTCVive 交互事件

下一篇：Hrbust 2222 应援团补完计划【并查集+思维】好题~