---

title: word ladder總結
categories: LeetCode
tags:

• 算法
• LeetCode
  comments: true
  date: 2016-10-16 09:42:30
  ---

題意

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

思路

因為上一個詞到下一個詞之間，變化的只是一個字母，因此只需遍歷所有字母，進行替換即可；

利用BFS的思想，將改變后的字符串存進隊列中，進行下一次的循環。

題解

這個的題解有很多種，但是其實都是使用了最基本的BFS思想；

交換隊列，計算層數

int ladderLength(string begin, string end, unordered_set<string>& wordList) {// 當前層，下一層queue<string> current, next;// 判重unordered_set<string> visited;// 層次int level = 0;bool found = false;// 有點像內聯函數auto state_is_target = [&](const string &s) {return s == end;};auto state_extend = [&](const string &s) {vector<string> result;for (size_t i = 0; i < s.size(); ++i) {string new_word(s);for (char c = 'a'; c <= 'z'; c++) {if (c == new_word[i]) continue;swap(c, new_word[i]);if (wordList.count(new_word) > 0 && !visited.count(new_word)) {result.push_back(new_word);visited.insert(new_word);}swap(c, new_word[i]);}}return result;};current.push(begin);while (!current.empty() && !found) {++level;while (!current.empty() && !found) {const string str = current.front();current.pop();const auto& new_states = state_extend(str);for (const auto& state : new_states) {next.push(state);if (state_is_target(state)) {//找到found = true;break;}}}swap(next, current);}if (found) return level + 1;else return 0; }

總結：

使用了匿名函數，其中命名的state_is_target,state_extend是函數模版，分別做的操作就是判斷字符串是否相等，返回字符串BFS遍歷的下一層的數組；

同時用了兩層循環，外循環用于計算層數和交換隊列，內循環用于計算找到結尾字符串；

一個隊列

/*** 改變單詞中的字母， 查看是否存在** @param word <#word description#>* @param wordDict <#wordDict description#>* @param toVisit <#toVisit description#>*/ void addNextWords(string word, unordered_set<string>& wordDict, queue<string>& toVisit) {// 刪除wordDict中的word，因為相同的沒有用wordDict.erase(word);for (int i = 0; i < (int)word.length(); i++) {// 記錄下word的字母char letter = word[i];// 變換word中每個字母，一個一個字母的查找是否匹配，因為只能替換一個字母for (int j = 0; j < 26; j++) {word[i] = 'a' + j;// 找到后加入訪問過的隊列，并從wordDict中刪除if (wordDict.find(word) != wordDict.end()) {toVisit.push(word);wordDict.erase(word);}}// 變換回去word[i] = letter;} } /*** 使用BFS** @param beginWord <#beginWord description#>* @param endWord <#endWord description#>* @param wordDict <#wordDict description#>** @return <#return value description#>*/ int ladderLength2(string beginWord, string endWord, unordered_set<string>& wordDict) {// 加載最后的單詞wordDict.insert(endWord);queue<string> toVisit;addNextWords(beginWord, wordDict, toVisit);// 從2開始，是因為需要經歷開始和結尾的兩個字母int dist = 2;// toVisit中存儲的是通過改變一個字母就可以到達wordDict中存在的字符串while (!toVisit.empty()) {int num = (int)toVisit.size();for (int i = 0; i < num; i++) {string word = toVisit.front();toVisit.pop();if (word == endWord) return dist;addNextWords(word, wordDict, toVisit);}dist++;}return 0; }

總結：

同樣是計算BFS的層數；

兩個指針

/*** 使用兩個指針和BFS** @param beginWord <#beginWord description#>* @param endWord <#endWord description#>* @param wordDict <#wordDict description#>** @return <#return value description#>*/ int ladderLength3(string beginWord, string endWord, unordered_set<string>& wordDict) {unordered_set<string> head, tail, *phead, *ptail;head.insert(beginWord);tail.insert(endWord);int dist = 2;// 將phead指向更小size的unordered_set以便減少運行時間while (!head.empty() && !tail.empty()) {if (head.size() < tail.size()) {phead = &head;ptail = &tail;}else {phead = &tail;ptail = &head;}unordered_set<string> temp;for (auto iterator = phead->begin(); iterator != phead->end(); iterator++) {string word = *iterator;wordDict.erase(word);// 原理和上面一樣，更換其中的字符，for (int i = 0; i < (int)word.length(); i++) {char letter = word[i];for (int k = 0; k < 26; k++) {word[i] = 'a' + k;if (ptail->find(word) != ptail->end())return dist;if (wordDict.find(word) != wordDict.end()) {temp.insert(word);wordDict.erase(word);}}word[i] = letter;}}dist++;swap(*phead, temp);}return 0; }

總結：

兩個指針指向了unordered_set的head和tail，其做法和第一種方法是相通的，只不過一個用了unordered_set，同時在循環前面還加上了根據數組大小判斷指針指向不同的數組；

使用類

class WordNode { public:string word;int numSteps;public:WordNode(string w, int n) {this->word = w;this->numSteps = n;} }; /*** 使用類去處理記錄數據,和前面的思想是類似的** @param beginWord <#beginWord description#>* @param endWord <#endWord description#>* @param wordDict <#wordDict description#>** @return <#return value description#>*/ int ladderLength4(string beginWord, string endWord, unordered_set<string>& wordDict) {queue<WordNode*> queue;queue.push(new WordNode(beginWord, 1));wordDict.insert(endWord);while (!queue.empty()) {WordNode * top = queue.front();queue.pop();string word = top->word;if (word == endWord) {return top->numSteps;}for (int i = 0; i < word.length(); i++) {char temp = word[i]; //先記錄后面還有改回來for (char c = 'a'; c <= 'z'; c++) {if (temp != c) {word[i] = c;}if (wordDict.find(word) != wordDict.end()) {queue.push(new WordNode(word, top->numSteps + 1));wordDict.erase(word);}}word[i] = temp;}}return 0; }

總結：

使用類去記錄每個字符串的單前遍歷的層數，本質還是計算層數，只不過用類去保存，這樣的好處就是減少了一些計算代碼；

題意

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.

思路

肯定需要兩個數組，一個用來存儲當前已經存在的字符串，一個用來存放遍歷結果的字符串，最后兩者進行交換，直到遍歷當前數組為空；還有一個重點在于可以利用鄰接矩陣的思想，用map存儲字符串和數組一一對應關系，最后根據順序進行輸出map即可；

代碼

vector<string> temp_path; vector<vector<string>> result_path;/*** 生成路徑（從后往前）** @param unordered_map<string <#unordered_map<string description#>* @param path <#path description#>* @param start <#start description#>* @param end <#end description#>*/ void generatePath(unordered_map<string, unordered_set<string>>& path, const string& start, const string& end) {temp_path.push_back(start);if (start == end) {vector<string> ret = temp_path;reverse(ret.begin(), ret.end());result_path.push_back(ret);return ;}for (auto it = path[start].begin(); it != path[start].end(); it++) {generatePath(path, *it, end);temp_path.pop_back();} }/***** @param beginWord <#beginWord description#>* @param endWord <#endWord description#>* @param wordList <#wordList description#>** @return <#return value description#>*/ vector<vector<string>> findLadders(string beginWord, string endWord, unordered_set<string> &wordList) {temp_path.clear();result_path.clear();unordered_set<string> current_step;unordered_set<string> next_step;unordered_map<string, unordered_set<string>> path;unordered_set<string> unvisited = wordList; // 記錄還沒有訪問過的結點if (unvisited.count(beginWord) > 0)unvisited.erase(beginWord);// 未訪問過的值增加結尾字符串，開始處加入起點字符串unvisited.insert(endWord);current_step.insert(beginWord);while (current_step.count(endWord) == 0 && unvisited.size() > 0) {// 遍歷當前層的所有元素for (auto cur = current_step.begin(); cur != current_step.end(); cur++) {string word = *cur;// 給字符串中的每個字符都替換字母for (int i = 0; i < beginWord.size(); i++) {for (int j = 0; j < 26; j++) {string tmp = word;// 相等情況下if (tmp[i] == 'a' + j) {continue;}tmp[i] = 'a' + j;// 表明字典中存在該字符串，可以到達下一步if (unvisited.count(tmp) > 0) {next_step.insert(tmp);path[tmp].insert(word);}}}}// 表明下一層中已經不存在任何沒有訪問過的if (next_step.empty()) {break;}// 清除所有沒有訪問過的值for (auto it = next_step.begin(); it != next_step.end(); it++) {unvisited.erase(*it);}current_step = next_step;next_step.clear();}// 存在結果if (current_step.count(endWord) > 0) {generatePath(path, endWord, beginWord);}return result_path; }/*** 建立樹** @param forward <#forward description#>* @param backward <#backward description#>* @param dict <#dict description#>* @param unordered_map<string <#unordered_map<string description#>* @param tree <#tree description#>* @param reversed <#reversed description#>** @return <#return value description#>*/ bool buildTree(unordered_set<string> &forward, unordered_set<string> &backward, unordered_set<string> &dict, unordered_map<string, vector<string> > &tree, bool reversed) {if (forward.empty()) return false;// 如果開頭的長度比結尾長，則從結尾開始找到開頭if (forward.size() > backward.size())return buildTree(backward, forward, dict, tree, !reversed);// 存在開頭和結尾則刪除for (auto &word: forward) dict.erase(word);for (auto &word: backward) dict.erase(word);unordered_set<string> nextLevel; // 存儲樹的下一層bool done = false; //是否進一步搜索for (auto &it: forward) //從樹的當前層進行遍歷{string word = it;for (auto &c: word){char c0 = c; //存儲初始值for (c = 'a'; c <= 'z'; ++c){if (c != c0){// 說明找到最終結果if (backward.count(word)){done = true; //找到!reversed ? tree[it].push_back(word) : tree[word].push_back(it); //keep the tree generation direction consistent;}// 說明還沒找到最終結果但是在字典中找到else if (!done && dict.count(word)){nextLevel.insert(word);!reversed ? tree[it].push_back(word) : tree[word].push_back(it);}}}c = c0; //restore the word;}}return done || buildTree(nextLevel, backward, dict, tree, reversed); } /*** 生成路徑** @param beginWord <#beginWord description#>* @param endWord <#endWord description#>* @param unordered_map<string <#unordered_map<string description#>* @param tree <#tree description#>* @param path <#path description#>* @param paths <#paths description#>*/ void getPath(string &beginWord, string &endWord, unordered_map<string, vector<string> > &tree, vector<string> &path, vector<vector<string> > &paths) //using reference can accelerate; {if (beginWord == endWord) paths.push_back(path); //till the end;else{for (auto &it: tree[beginWord]){path.push_back(it);getPath(it, endWord, tree, path, paths); //DFS retrieving the path;path.pop_back();}} }vector<vector<string>> findLadders2(string beginWord, string endWord, unordered_set<string> &dict) {vector<vector<string> > paths;vector<string> path(1, beginWord);if (beginWord == endWord){paths.push_back(path);return paths;}// 分別存儲開頭和結尾unordered_set<string> forward, backward;forward.insert(beginWord);backward.insert(endWord);unordered_map<string, vector<string> > tree;// 用來判斷是從開頭找到結尾還是從結尾找到開頭，因為會從長度短的一方開始進行查找bool reversed = false;if (buildTree(forward, backward, dict, tree, reversed))getPath(beginWord, endWord, tree, path, paths);return paths; }bool test() {unordered_set<string> words = {"hot","dot","dog","lot","log"};string start = "hit", end = "cog";vector<vector<string>> result = findLadders2(start, end, words);for (auto i = 0; i < result.size(); ++i) {for (auto j = 0; j < result[0].size(); ++j) {cout << result[i][j] << "->";}cout << endl;}return true; }

這兩種方法其實是一樣的；

轉載于:https://www.cnblogs.com/George1994/p/6399868.html

總結

以上是生活随笔為你收集整理的word-ladder总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。