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 應援團補完計劃【并查集+思維】好題~