这道题非常难。
之前的题目我提到过一次用两个vector来做层序遍历的,就是由于这道题。要想最后恢复出单词变换的路径,就须要事先保存,依据dp中路径恢复的启示,保存的应该是一个单词的前一个变换节点。可能有非常多个单词都能变换到当前单词,因此应该是一个set。用一个二维的vector保存当前能够变换到的单词和变换出这些单词单词。每一维的vector存放的都是一个set。设存放当前可訪问单词的vector下标是current,存放变幻出这些单词的vector下标是pre,那么每一轮要開始更新current之前,都要从字典里删除pre中存放的单词。这样做比直接用一个set存放訪问过的单词要快,也更加节省空间,由于字典的规模在不断变小。由于要打印出所有的路径,所以不是说遇到目标单词就直接结束,而应该等着这一层的变换所有结束之后才行。假设在这一层变换之后发现了目标单词,那么就開始打印路径。
递归打印路劲跟其它题目的写法没有太多不同,主要是注意假设用引用做的话要合适的回退,且最后是反向打印的,应该把结果reverse一下再放到结果集中。
实现的时候还发现一个问题,我之前一直以为在訪问方面vector应该是最快的,所以就把全部东西都弄成了vector,然后下标訪问,结果超时了。假设要顺序訪问的话,迭代器要比随机訪问好。
class Solution {
public:
vector<vector<string> > res;
void getPaths(unordered_map<string, vector<string> > &predict, vector<string> &tpres, string &word){
if(predict[word].size() == 0){
tpres.push_back(word);
vector<string> pres = tpres;
reverse(pres.begin(), pres.end());
res.push_back(pres);
tpres.pop_back();
return;
}
tpres.push_back(word);
for(auto it=predict[word].begin();it!=predict[word].end();++it)
getPaths(predict, tpres, *it);
tpres.pop_back();
}
vector<vector<string> > findLadders(string start, string end, unordered_set<string> &dict) {
unordered_map<string, vector<string> > predict;
int cu = 0, pre = 1, len = start.length();
vector<unordered_set<string> > candi(2);
vector<string> tpres;
predict[start] = tpres;
candi[0].insert(start);
string word;
while(true){
cu = !cu;
pre = !pre;
for(auto it=candi[pre].begin();it!=candi[pre].end();++it){
dict.erase(*it);
}
candi[cu].clear();
for(auto it=candi[pre].begin();it!=candi[pre].end();++it){
for(int pos=0;pos<len;pos++){
word = *it;
for(char c='a';c<='z';c++){
if(word[pos] == c) continue;
word[pos] = c;
if(dict.count(word)>0){
candi[cu].insert(word);
predict[word].push_back(*it);
}
}
}
}
if(candi[cu].size() == 0) return res;
if(candi[cu].count(end))
break;
}
getPaths(predict, tpres, end);
return res;
}
};