本文主要是介绍word ladder，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://leetcode.com/onlinejudge#question_126
原题：
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
- Only one letter 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"]
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.
思路：
其实解题思路和Word Ladder完全一样，BFS，但是麻烦的是要返回所有的路径。
所以没办法，只能把每个单词所对应的前驱单词记录下来，当然有可能有多个，那么
就用一个vector<string>存储好，有这些记录就可以重构路径了。
代码：
- class Solution {
- public:
- vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
- // Start typing your C/C++ solution below
- // DO NOT write int main() function
- pathes.clear();
- dict.insert(start);
- dict.insert(end);
- vector<string> prev;
- unordered_map<string, vector<string> > traces;
- for (unordered_set<string>::const_iterator citr = dict.begin();
- citr != dict.end(); citr++) {
- traces[*citr] = prev;
- }
- vector<unordered_set<string> > layers(2);
- int cur = 0;
- int pre = 1;
- layers[cur].insert(start);
- while (true) {
- cur = !cur;
- pre = !pre;
- for (unordered_set<string>::const_iterator citr = layers[pre].begin();
- citr != layers[pre].end(); citr++)
- dict.erase(*citr);
- layers[cur].clear();
- for (unordered_set<string>::const_iterator citr = layers[pre].begin();
- citr != layers[pre].end(); citr++) {
- for (int n=0; n<(*citr).size(); n++) {
- string word = *citr;
- int stop = word[n] - 'a';
- for (int i=(stop+1)%26; i!=stop; i=(i+1)%26) {
- word[n] = 'a' + i;
- if (dict.find(word) != dict.end()) {
- traces[word].push_back(*citr);
- layers[cur].insert(word);
- }
- }
- }
- }
- if (layers[cur].size() == 0)
- return pathes;
- if (layers[cur].count(end))
- break;
- }
- vector<string> path;
- buildPath(traces, path, end);
- return pathes;
- }
- private:
- void buildPath(unordered_map<string, vector<string> > &traces,
- vector<string> &path, const string &word) {
- if (traces[word].size() == 0) {
- path.push_back(word);
- vector<string> curPath = path;
- reverse(curPath.begin(), curPath.end());
- pathes.push_back(curPath);
- path.pop_back();
- return;
- }
- const vector<string> &prevs = traces[word];
- path.push_back(word);
- for (vector<string>::const_iterator citr = prevs.begin();
- citr != prevs.end(); citr++) {
- buildPath(traces, path, *citr);
- }
- path.pop_back();
- }
- vector<vector<string> > pathes;
- };
这篇关于word ladder的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
