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"] ]
思路：
我自己用回溯做，结果超时了。代码和注释如下： 很长
#include#include #include #include #include #include #include using namespace std;class Solution {public: vector > findLadders(string start, string end, unordered_set &dict) { vector > ans; vector hash; //记录单词是否已经生成 vector X; vector > S; vector hashlength; //记录在k = 0 - ... 时 hash 的长度 方便弹出 int minlen = 1000; int k = 0; hash.push_back(start); hashlength.push_back(1); if(S.size() <= k) { S.push_back(vector ()); } S[k].push_back(start); while(k >= 0) { while(!S[k].empty()) { X.push_back(S[k].back()); S[k].pop_back(); if(onedifferent(X.back(), end)) { X.push_back(end); if(k == minlen) //只存长度最短的 { ans.push_back(X); } if(k < minlen) //如果有新的最短长度 ans清空，压入新的最短答案 { minlen = k; ans.clear(); ans.push_back(X); } } else if(k < minlen) //k如果>= minlen 那么后面的结果肯定大于最短长度 { k++; if(S.size() <= k) //如果S的长度不够 扩大S长度 { S.push_back(vector ()); } if(hashlength.size() <= k)//如果hashlength的长度不够 扩大其长度 { hashlength.push_back(0); } unordered_set ::iterator it; for(it = dict.begin(); it != dict.end(); it++) //对字典中的数字遍历，得到下一个长度可以用的备选项 { if(onedifferent(X.back(), *it) && (find(hash.begin(), hash.end(), *it) == hash.end())) { hashlength[k]++; hash.push_back(*it); S[k].push_back(*it); } } } } k--; while(k >= 0 && hashlength[k]) //把当前层压入hash的值都弹出 { hash.pop_back(); hashlength[k]--; } while(k >= 0 && X.size() > k) //把当前层压入X的值弹出 { X.pop_back(); } } return ans; } bool onedifferent(string s1, string s2) //判断s1是否可以只交换一次得到s2 { int diff = 0; for(int i = 0; i < s1.size(); i++) { if(s1[i] != s2[i]) diff++; } return (diff == 1); } };int main(){ Solution s; unordered_set dict; dict.insert("hot"); dict.insert("dot"); dict.insert("dog"); dict.insert("lot"); dict.insert("log"); string start = "hit"; string end = "cog"; vector > ans = s.findLadders(start, end, dict); return 0;}
别人的思路：我没怎么看，只知道是用图的思想 速度也不快 差不多1000ms的样子
class Solution {public: vector > helper(unordered_map > &pre,string s,unordered_map &visit,string start){ vector > ret,ret1;vector t_ret; if(s==start) {t_ret.push_back(s);ret.push_back(t_ret);return ret;} for ( auto it = pre[s].begin(); it != pre[s].end(); ++it ){ ret1=helper(pre,*it,visit,start); for(int i=0;i > findLadders(string start, string end, unordered_set &dict) { unordered_map > graph;unordered_map visit;unordered_map > pre; vector > ret; vector t_ret; if(start==end){t_ret.push_back(start);t_ret.push_back(end);ret.push_back(t_ret);return ret;} dict.insert(start);dict.insert(end); for ( auto it = dict.begin(); it != dict.end(); ++it ){ string t=*it; visit[t]=0; for(int i=0;i 0) graph[t].push_back(tt); } } queue myq; myq.push(start); while(!myq.empty()){ for(int i=0;i 0&&visit[graph[myq.front()][i]]>=visit[myq.front()]+1){ if(visit[graph[myq.front()][i]]>visit[myq.front()]+1){ visit[graph[myq.front()][i]]=visit[myq.front()]+1; pre[graph[myq.front()][i]].push_back(myq.front()); }else pre[graph[myq.front()][i]].push_back(myq.front());; } } visit[start]=1; myq.pop(); } if(visit[end]==0) return ret; ret=helper(pre,end,visit,start); return ret; }};