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"]
]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
思路：这是一道BFS的题。保存所有的最短的路径，以下我的解法大数据时超出内存。
class Solution {
public:
bool isLadder(string a, string b) {
int co = 0;
int i;
for (i=0; i<a.size(); ++i) {
if (a[i] != b[i]) {
co++;
}
}
if (co>1) {
return false;
}
return true;
}
struct Data {
<span style="white-space:pre"> </span>string str;
<span style="white-space:pre"> </span>stack<string> strSeq;
<span style="white-space:pre"> </span>Data(string a):str(a) {
<span style="white-space:pre"> </span>strSeq.push(a);
<span style="white-space:pre"> </span>}
};
vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
vector<vector<string> > res;
vector<string> per;
if (isLadder(start, end)) {
per.push_back(start);
per.push_back(end);
res.push_back(per);
return res;
}
unordered_set<string> myDict = dict;
Data dEnd(end);
queue<Data> pre, back;
back.push(dEnd);
int i,j;
while (!back.empty()) {
<span style="white-space:pre"> </span>while (!pre.empty()) {
<span style="white-space:pre"> </span>pre.pop();
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>bool flag = false;
<span style="white-space:pre"> </span>while (!back.empty()) {
<span style="white-space:pre"> </span>Data top = back.front();
<span style="white-space:pre"> </span>back.pop();
<span style="white-space:pre"> </span>for (i=0; i<top.str.size(); ++i) {
<span style="white-space:pre"> </span>for (j=0; j<26; ++j) {
<span style="white-space:pre"> </span>string tmp = top.str;
<span style="white-space:pre"> </span>tmp[i] = 'a' + j;
<span style="white-space:pre"> </span>if ((tmp!=top.str) && (myDict.find(tmp)!=myDict.end())) {
<span style="white-space:pre"> </span>Data dTmp(tmp);
<span style="white-space:pre"> </span>dTmp.strSeq = top.strSeq;
<span style="white-space:pre"> </span>dTmp.strSeq.push(tmp);
<span style="white-space:pre"> </span>pre.push(dTmp);
<span style="white-space:pre"> </span>if (isLadder(tmp, start)) {
<span style="white-space:pre"> </span>flag = true;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>back = pre;
<span style="white-space:pre"> </span>if (flag) {
<span style="white-space:pre"> </span>break;
<span style="white-space:pre"> </span>}
}
while (!back.empty()) {
<span style="white-space:pre"> </span>Data top = back.front();
<span style="white-space:pre"> </span>back.pop();
<span style="white-space:pre"> </span>vector<string> vStr;
<span style="white-space:pre"> </span>unordered_set<string> sStr;
<span style="white-space:pre"> </span>vStr.push_back(start);
<span style="white-space:pre"> </span>string cmp = "";
<span style="white-space:pre"> </span>while (!top.strSeq.empty()) {
<span style="white-space:pre"> </span>cmp = top.strSeq.top();
<span style="white-space:pre"> </span>top.strSeq.pop();
<span style="white-space:pre"> </span>vStr.push_back(cmp);
<span style="white-space:pre"> </span>if (sStr.find(cmp) != sStr.end()) {
<span style="white-space:pre"> </span>break;
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>sStr.insert(cmp);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>if ((sStr.size() == vStr.size()-1) && isLadder(cmp, start)) {
<span style="white-space:pre"> </span>res.push_back(vStr);
<span style="white-space:pre"> </span>}
}
/*for (i=0; i<res.size(); ++i) {
<span style="white-space:pre"> </span>for (j=0; j<res[i].size(); ++j) {
<span style="white-space:pre"> </span>cout << res[i][j] << " ";
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>cout << endl;
}*/
return res;
}
};
以上的解法超出了空间限制。改进：可以设一个path，key为当前单词，value表示当前单词的后驱单词。再分别设置变量curStep和nextStep，表示层序变量的上一层和下一层。为了防止字典中的单词多次使用，每比较完一层需要将字典中该层出现过的单词过滤掉。因此代码如下：（代码思路参考了网上的资料）
class Solution {
public:
vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
map<string,vector<string> > path;
unordered_set<string>rightside=dict;
rightside.erase(start);
unordered_set<string>curStep;
unordered_set<string>nextStep;
curStep.insert(start);
while(curStep.find(end)==curStep.end()&&!rightside.empty())
{
for(auto iter_us_cur=curStep.begin();iter_us_cur!=curStep.end();++iter_us_cur)
{
string temp;
for(int i=0;i<(*iter_us_cur).length();++i)
{
for(int j = 0;j<26;j++)
{
temp = *iter_us_cur;
if(temp[i]!=('a'+j))
{
temp[i] = ('a'+j);
}
if(rightside.find(temp) != rightside.end())
{
nextStep.insert(temp);
if(path.find(*iter_us_cur)==path.end())
{
vector<string> V;
path.insert(make_pair(*iter_us_cur,V));
}
path[*iter_us_cur].push_back(temp);
}
}
}
}
if(nextStep.empty())break;
for(auto iter_set=nextStep.begin();iter_set!=nextStep.end();++iter_set)
{
rightside.erase(*iter_set);
}
curStep = nextStep;
nextStep.clear();
}
vector<vector<string> > result;
vector<string> temp;
if(curStep.find(end)!=curStep.end())
{
output(path,start,end,result,temp);
}
return result;
}
void output(map<string,vector<string> >&path,string start,string end,vector<vector<string> >&result,vector<string> & temp)
{
temp.push_back(start);
if(start==end)
{
result.push_back(temp);return;
}
vector<string>::iterator iter_v;
for(iter_v=path[start].begin();iter_v!=path[start].end();++iter_v)
{
output(path,*iter_v,end,result,temp);temp.pop_back();
}
}
};