先写一下超时代码,练一下dfs
class Solution { public: vector<string> path; unordered_set<string> visited; vector<vector<string>> res; 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 if(!path.empty()) path.pop_back(); if(!visited.empty()) visited.clear(); while(!res.empty()) res.pop_back(); dfs(start,end,dict); int min=0x7fffffff; for(int i=0;i<res.size();i++){ if(res[i].size()<min) min=res[i].size(); } vector<vector<string>> ans; for(int i=0;i<res.size();i++){ if(res[i].size()==min) ans.push_back(res[i]); } return ans; } void dfs(string start,string end,unordered_set<string> &dict){ visited.insert(start); path.push_back(start); int len=start.length(); for(int i=0;i<len;i++) for(int j=0;j<26;j++){ string str=start; str[i]='a'+j; if(str!=start&&dict.find(str)!=dict.end()&&visited.find(str)==visited.end()){ if(str==end){//注意这儿不能return,因为当前节点不是最后一层的节点(是倒数第二层的节点),return的话会跑到倒数第三层的节点上去 path.push_back(str); res.push_back(path); path.pop_back(); }else{ dfs(str,end,dict); path.pop_back(); visited.erase(str); } } } } };