广度搜索 -- 9.1 Word Ladder -- 求是否有解 -- 图解

/**********************************************************************************************************

当题目看不出任何规律，既不能用分治，贪心，也不能用动规时，这时候万能方法——搜就

派上用场了。搜索分为广搜和深搜，广搜里面又有普通广搜，双向广搜， A* 搜索等。深搜里面又有普通深搜，回溯法等。

广搜和深搜非常类似（除了在扩展节点这部分不一样），二者有相同的框架，如何表示状

如何扩展状态？如何判重？尤其是判重，解决了这个问题，基本上整个问题就解决了。

描述

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence

from start to end, such that:

• Only one leer can be changed at a time

• Each intermediate word must exist in the dictionary

For example, Given:

start = "hit"

end = "cog"

dict = ["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.**********************************************************************************************************/

class Solution{public:typedef string state_t;int ladderLength(string start, string end, const unordered_set<string> &dict){if (start.size() != end.size()) return 0;if (start.empty() || end.empty()) return 0;queue<string > next, current;// 下一层 ，当前层unordered_set<string> visited; //判断重复int level = 0;unordered_map<string, string> father;bool found = false;current.push(start);while (!current.empty() && !found){++level;while (!current.empty() && !found){const string str(current.front());current.pop();for (size_t i = 0; i < str.size(); i++){string new_word(str);for (char c = 'a'; c < 'z'; c++){ //start = "hit"if (c == new_word[i]) continue;swap(c, new_word[i]);if (new_word == end){found = true;father[new_word] = str;//??}if (dict.count(new_word) > 0 && !visited.count(new_word)){next.push(new_word);visited.insert(new_word);father[new_word] = str;}swap(c, new_word[i]);}}}swap(next, current);}if (found) return level + 1;else return 0;}};

参考资料：

LeetCode题解