/********************************************************************************************************** 当题目看不出任何规律，既不能用分治，贪心，也不能用动规时，这时候万能方法——搜就 派上用场了。搜索分为广搜和深搜，广搜里面又有普通广搜，双向广搜， 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 leer 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题解
