Word Ladder II
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.
Leetcode 第一难题,六星级! 帆船酒店来了!
难点考点:
1 知道什么时候去掉重复,会使用set容器避免重复
2 高级层序遍历树应用
3 适当时候去掉字典中的单词避免重复
4 知道什么时候结束层序
5 利用高级数据结构保存结果,本程序使用unordered_map<string, vector<string> >
6 使用递归回溯法,利用高级数据结构,构造最终结果
每一点几乎都可以成为一个大题,都糅合在一起了,加上各个细节,那么就构成了一个六星级难题了。
注意细节:
1 上一层的单词要删掉,否则会有回路,形成无线循环
2 下一层保存单词不能重复,否则会有很多多余的单词处理,造成time limit excessed
新思维解决问题:
子节点可以重复,但是只保留一个子节点,不过要保留这个子节点的多个父母节点,但是子节点只能保留一份。
要怎么完成这个操作呢?
1 使用set保留子节点
2 使用map<string, vector<string> > 保留父母节点,这样确保只有一个string子节点,而可以有多个父母节点vector<string>
形成path的时候,因为最终根节点肯定是start,所以一个孩子节点分别从多个父母节点回溯,都必然会到达start根节点
//2014-2-18 update vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) { vector<vector<string> > rs; unordered_map<string, vector<string> > ump_sv; dict.erase(start); dict.erase(end); vector<string> qu[2]; set<string> sst; qu[0].push_back(start); bool idx = false; bool finished = false; while (!qu[idx].empty()) { while (!qu[idx].empty()) { string s = qu[idx].back(); for (int i = 0; i < s.length(); i++) { char a = s[i]; for (char az = 'a'; az <= 'z'; az++) { s[i] = az; if (s == end) { finished = true; ump_sv[s].push_back(qu[idx].back()); } else if (dict.count(s)) { ump_sv[s].push_back(qu[idx].back()); qu[!idx].push_back(s); } } s[i] = a; }//for qu[idx].pop_back(); }//while if (finished) break; idx = !idx; sst.clear(); sst.insert(qu[idx].begin(), qu[idx].end()); qu[idx].assign(sst.begin(), sst.end()); for (auto x:qu[idx]) dict.erase(x); }//while if (!ump_sv.count(end)) return rs; vector<string> tmp(1, end); constructLadder(rs, tmp, ump_sv, start, end); return rs; } void constructLadder(vector<vector<string> > &rs, vector<string> &tmp, unordered_map<string, vector<string> > &ump_sv, string &start, string &cur) { if (cur == start) { rs.push_back(tmp); reverse(rs.back().begin(), rs.back().end()); return; } vector<string> v = ump_sv[cur]; for (int i = 0; i < v.size(); i++) { tmp.push_back(v[i]); constructLadder(rs, tmp, ump_sv, start, v[i]); tmp.pop_back(); } }