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.
思路转载 http://www.cnblogs.com/TenosDoIt/p/3443512.html
分析：本题主要的框架和上一题是一样，但是还要解决两个额外的问题：一、 怎样保证求得所有的最短路径；二、 怎样构造这些路径
第一问题：
- 不能像上一题第二点注意那样，找到一个单词相邻的单词后就立马把它从字典里删除，因为当前层还有其他单词可能和该单词是相邻的，这也是一条最短路径，比如hot->hog->dog->dig和hot->dot->dog->dig，找到hog的相邻dog后不能立马删除，因为和hog同一层的单词dot的相邻也是dog，两者均是一条最短路径。但是为了避免进入死循环，再hog、dot这一层的单词便利完成后dog还是得从字典中删除。即等到当前层所有单词遍历完后，和他们相邻且在字典中的单词要从字典中删除。
- 如果像上面那样没有立马删除相邻单词，就有可能把同一个单词加入bfs队列中，这样就会有很多的重复计算（比如上面例子提到的dog就会被2次加入队列）。因此我们用一个哈希表来保证加入队列中的单词不会重复，哈希表在每一层遍历完清空（代码中hashtable）。
- 当某一层的某个单词转换可以得到end单词时，表示已经找到一条最短路径，那么该单词的其他转换就可以跳过。并且遍历完这一层以后就可以跳出循环，因为再往下遍历，肯定会超过最短路径长度
第二个问题：
- 为了输出最短路径，我们就要在比bfs的过程中保存好前驱节点，比如单词hog通过一次变换可以得到hot，那么hot的前驱节点就包含hog，每个单词的前驱节点有可能不止一个，那么每个单词就需要一个数组来保存前驱节点。为了快速查找因此我们使用哈希表来保存所有单词的前驱路径，哈希表的key是单词，value是单词数组。（代码中的unordered_map<string,vector<string> >prePath）
- 有了上面的前驱路径，可以从目标单词开始递归的构造所有最短路径（代码中的函数 ConstructResult）
class Solution {
public:
vector<vector<string> > findLadders(string start, string end, unordered_set<string>& dict)
{
vector<vector<string> > result;
if(start.empty() || end.empty() )
return result;
if(start.size() != end.size())
return result;
size_t size = start.size();
unordered_set<string> cur, next;//use set to aviod add duplicate element
unordered_map<string, vector<string> > father;
unordered_set<string> visited; // 判重
cur.insert(start);
bool found = false;
while(!cur.empty() && !found)
{
for (const auto& word : cur)
visited.insert(word);
for(unordered_set<string>::iterator it = cur.begin(); it != cur.end(); it++)
{
string curStr= *it;
//cout << "=========" <<curStr <<"========================" <<endl;
for(int i = ; i< size; i++)
{
for(char j = 'a'; j <= 'z'; j++ )
{
string nextStr = curStr;
if(nextStr[i] == j)
continue;
nextStr[i] = j;
if(nextStr.compare(end) == )
{
//if found, just traverse this layer, not go to next layer
found = true;
father[nextStr].push_back(curStr);
}
#if 0
cout << "nextStr = " << nextStr<< endl;
cout << "nextStr [i] = " << nextStr[i]<< endl;
cout << "i = " << i<< endl;
cout << "j = " << j<< endl;
#endif
//if(dict.find(nextStr) != dict.end() && cur.find(nextStr) == cur.end())
if(dict.find(nextStr) != dict.end() && !visited.count(new_word))
// must add "&& cur.find(nextStr) == cur.end()"
// to avoid the same level 's elemnt point each other
// for example hot --> dot
// hot --> lot
// but when you travel to dot, may happen dot --> lot
// but when you travel to lot, may happen lot --> dot
// so when add it to next, we must confirm that lot is not in this level
{
//cout << "insert\t" << nextStr<< "\tto next queue" << endl;
next.insert(nextStr);
father[nextStr].push_back(curStr);
}
}
}
}
// remove the cur layer's elements form dict
for(unordered_set<string>::iterator it = cur.begin(); it != cur.end(); it++)
{
string tmp = *it;
if(dict.find(tmp) != dict.end())
{
dict.erase(dict.find(tmp));
//cout << "erase \t" << tmp <<endl;
}
}
cur.clear();
swap(cur, next);
}
vector<string> path;
for(unordered_map<string, vector<string> >::iterator it = father.begin(); it != father.end(); it++)
{
string str =(*it).first;
vector<string> vect =(*it).second;
//cout << "map key :" << str <<endl;
for(int i = ; i < vect.size(); i++)
{
//cout << "\tmap value:" << vect[i]<<endl;
}
}
genPath(start, end, path, father, result);
return result;
}
void genPath(string start, string end, vector<string>& path, unordered_map<string, vector<string> >map, vector<vector<string> >& result)
{
path.push_back(end);
if(start == end)
{
reverse(path.begin(), path.end());
result.push_back(path);
//printVector(path);
reverse(path.begin(), path.end());
}
else
{
int size = map[end].size();
for( int i = ; i < size; i++)
{
string str = map[end][i];
genPath(start, str, path, map, result);
}
}
path.pop_back();
}
};
大数据会超时，
转一个网上找的能通过的版本，随后在仔细分析差距在哪里吧。。
class Solution {
public:
vector<vector<string> > findLadders(string start, string end,
const unordered_set<string> &dict) {
unordered_set<string> current, next; // 当前层，下一层，用集合是为了去重
unordered_set<string> visited; // 判重
unordered_map<string, vector<string> > father; // 树
bool found = false;
auto state_is_target = [&](const string &s) {return s == end;};
auto state_extend = [&](const string &s) {
unordered_set<string> result;
for (size_t i = ; i < s.size(); ++i) {
string new_word(s);
for (char c = 'a'; c <= 'z'; c++) {
if (c == new_word[i]) continue;
swap(c, new_word[i]);
if ((dict.count(new_word) > || new_word == end) &&
!visited.count(new_word)) {
result.insert(new_word);
}
swap(c, new_word[i]); // 恢复该单词
}
}
return result;
};
current.insert(start);
while (!current.empty() && !found) {
// 先将本层全部置为已访问，防止同层之间互相指向
for (const auto& word : current)
visited.insert(word);
for (const auto& word : current) {
const auto new_states = state_extend(word);
for (const auto &state : new_states) {
if (state_is_target(state)) found = true;
next.insert(state);
father[state].push_back(word);
// visited.insert(state); // 移动到最上面了
}
}
current.clear();
swap(current, next);
}
vector<vector<string> > result;
if (found) {
vector<string> path;
gen_path(father, path, start, end, result);
}
return result;
}
private:
void gen_path(unordered_map<string, vector<string> > &father,
vector<string> &path, const string &start, const string &word,
vector<vector<string> > &result) {
path.push_back(word);
if (word == start) {
result.push_back(path);
reverse(result.back().begin(), result.back().end());
} else {
for (const auto& f : father[word]) {
gen_path(father, path, start, f, result);
}
}
path.pop_back();
}
};