Leetcode Word Ladder II

Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. 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 >

     6 使用递归回溯法，利用高级数据结构，构造最终结果

     每一点几乎都可以成为一个大题，都糅合在一起了，加上各个细节，那么就构成了一个六星级难题了。

     
     

     注意细节：
     1 上一层的单词要删掉，否则会有回路，形成无线循环
     

     2 下一层保存单词不能重复，否则会有很多多余的单词处理，造成time limit excessed

     
     

     新思维解决问题：
     子节点可以重复，但是只保留一个子节点，不过要保留这个子节点的多个父母节点，但是子节点只能保留一份。
     要怎么完成这个操作呢？
     1 使用set保留子节点
     2 使用map > 保留父母节点，这样确保只有一个string子节点，而可以有多个父母节点vector
     形成path的时候，因为最终根节点肯定是start，所以一个孩子节点分别从多个父母节点回溯，都必然会到达start根节点
     

     
     

     //2014-2-18 update
     	vector
             
              > findLadders(string start, string end, unordered_set
              
                &dict) { vector
               
                 > rs; unordered_map
                
                  > ump_sv; dict.erase(start); dict.erase(end); vector
                 
                   qu[2]; set
                  
                    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
                   
                     tmp(1, end); constructLadder(rs, tmp, ump_sv, start, end); return rs; } void constructLadder(vector
                    
                      > &rs, vector
                     
                       &tmp, unordered_map
                      
                        > &ump_sv, string &start, string &cur) { if (cur == start) { rs.push_back(tmp); reverse(rs.back().begin(), rs.back().end()); return; } vector
                       
                         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(); } }