[leetcode刷题系列]Word Ladder II

本文主要是介绍[leetcode刷题系列]Word Ladder II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题时间卡的还真是严啊- - 

先bfs一遍，标记没个单词属于哪一层， 然后从end开始往回走，就好了

string start, end;
unordered_map<string, int> lev;
void dfs(string now, vector<string> & stk, vector<vector<string> > & ret){if(now == start){vector<string> tmp(stk);tmp.push_back(now);reverse(tmp.begin(), tmp.end());ret.push_back(tmp);return ;}stk.push_back(now);for(int i = 0; i < now.size(); ++ i)for(char c = 'a'; c <= 'z'; ++ c){string next(now);next[i] = c;if(next == now)continue;if(lev.find(next) != lev.end() && lev[next] == lev[now] - 1){dfs(next, stk, ret);}}stk.pop_back();
}
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() functionvector<vector<string> > ret;if(start == end){ret.resize(1);ret[0].push_back(start);return ret;}::start = start;::end = end;lev.clear();queue<string> q;lev[start] = 0;q.push(start);while(!q.empty()){string now = q.front();q.pop();if(now == end)continue;for(int i = 0; i < now.size(); ++ i)for(char c = 'a'; c <= 'z'; ++ c){string next(now);next[i] = c;if(next == end || dict.find(next) != dict.end())if(lev.find(next) == lev.end()){lev[next] = lev[now] + 1;q.push(next);}}}vector<string> stk;dfs(end, stk, ret);return ret;}
};

这篇关于[leetcode刷题系列]Word Ladder II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---