首页 > 代码库 > Word Ladder II [leetcode]
Word Ladder II [leetcode]
本题有几个注意点:
1. 回溯找路径时。依据路径的最大长度控制回溯深度
2. BFS时,在找到end单词后,给当前层做标记find=true,遍历完当前层后结束。不须要遍历下一层了。
3. 能够将字典中的单词删除。替代visited的set,这样优化以后时间从1700ms+降到800ms+
代码例如以下:
class Solution { public: vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) { set<string> queue[2]; queue[0].insert(start); vector<vector<string>> res; bool find = false; int length = 1; bool cur = false; map<string, set<string>> mapping; //bfs while (queue[cur].size() && !find) { length++; for (set<string>::iterator i = queue[cur].begin(); i != queue[cur].end(); i++)//delete from dictionary dict.erase(*i); for (set<string>::iterator i = queue[cur].begin(); i != queue[cur].end(); i++) { for (int l = 0; l < (*i).size(); l++) { string word = *i; for (char c = ‘a‘; c <= ‘z‘; c++) { word[l] = c; if (dict.find(word) != dict.end()) { if (mapping.find(word) == mapping.end()) mapping[word] = set<string>(); mapping[word].insert(*i); if (word == end) find = true; else queue[!cur].insert(word); } } } } queue[cur].clear(); cur = !cur; } if (find) { vector<string> temp; temp.push_back(end); getRes(mapping, res, temp, start, length); } return res; } void getRes(map<string, set<string>> & mapping, vector<vector<string>> & res, vector<string> temp, string start, int length) { if (temp[0] == start) { res.push_back(temp); return; } if (length == 1) return;//recursion depth string word = temp[0]; temp.insert(temp.begin(), ""); for (set<string>::iterator j = mapping[word].begin(); j != mapping[word].end(); j++) { temp[0] = *j; getRes(mapping, res, temp, start, length - 1); } } };
Word Ladder II [leetcode]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。