首页 > 代码库 > Word Ladder II
Word Ladder II
这道题做了好长时间都没通过，参考了http://blog.csdn.net/niaokedaoren/article/details/8884938的实现，其中在求前驱单词记录时，申请的数组要采用vector<unordered_set<string>>这样，在判断是否结束时，查找效率更高，否则用前向单词记录表查找时效率会很低。
算法中的递归找paht可以用栈来避免递归，是一个优化点。
class Solution {public: vector<vector<string>> wordsladders; vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) { unordered_map<string,vector<string>> forword; dict.insert(end); InitData(forword,dict); bool ret; ret = GetTraces(forword,start,end,dict); if(ret == false) return wordsladders; vector<string> path; GetPath(end,forword,path); return wordsladders; } void GetPath(string& tempstr,unordered_map<string,vector<string>> &forword,vector<string>& path) { vector<string> result; path.push_back(tempstr); if(forword[tempstr].empty()) { result.resize(path.size()); copy(path.rbegin(), path.rend(),result.begin()); wordsladders.push_back(result); path.pop_back(); return ; } for(auto ite = forword[tempstr].begin(); ite!= forword[tempstr].end(); ite++) { GetPath(*ite,forword,path); } path.pop_back(); } void InitData(unordered_map<string,vector<string>> &forword,unordered_set<string> &dict) { unordered_set<string>::iterator ite; pair<string,vector<string>> temp; for(ite = dict.begin(); ite!= dict.end(); ite++) { temp.first = *ite; forword.insert(temp); } } bool GetTraces(unordered_map<string,vector<string>> &forword,string& start,string& end,unordered_set<string> &dict) { vector<unordered_set<string> > buf(2); int cur,pre; cur =0; pre =1; string tempstr; buf[0].insert(start); while(1) { cur = !cur; pre = !pre; for(auto ite = buf[pre].begin(); ite != buf[pre].end(); ite++) { dict.erase(*ite); } for(auto ite = buf[pre].begin(); ite!= buf[pre].end(); ite++) { for(int i = 0; i < (*ite).size(); i++) { tempstr = *ite; for(int j=0; j< 26;j++) { if(‘a‘+j == tempstr[i]) continue ; tempstr[i] = ‘a‘+j; if(dict.find(tempstr) == dict.end()) continue; forword[tempstr].push_back(*ite); buf[cur].insert(tempstr); } } } buf[pre].clear(); if(buf[cur].size() == 0) return false; if(buf[cur].count(end)) return true; } } };
Word Ladder II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。