Word Ladder II

 

Total Accepted: 6164 

Total Submissions: 58601

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.

此题是的扩展，要找出全部的最短变换序列。要注意的问题是在扩展当前字符串时。假设找到了一个在字典中出现的字符串。不能马上删除该字符串，由于可能当前扩展的字符串所在层中其它字符串也可能变换到同一个字符串，所以我用了一个容器来保存当前层节点能扩展到的字符串，当前层遍历完时才从字典中删除这些字符串。

尝试过用queue来保存当前队列，用vector来保存那些扩展到的字符串，可惜TLE。

class Solution {public:    vector
      
       
        > findLadders(string start, string end, unordered_set
        
          &dict) {        if (start == end) {            vector
         
           v = {start};            ret.push_back(v);            return ret;        }        if (dict.empty())            return ret;        //Use vector to implement bfs operation        queue
          
            q;        unordered_map
           
            > preStrMap; q.push(start); dict.erase(start); int currLevelLens = 1, nextLevelLens, head(0); string headStr, str; bool found = false; while (currLevelLens) { nextLevelLens = 0; vector
            
              levelStrs; while (currLevelLens--) { // Traverse the node of current level headStr = q.front(); q.pop(); for (int i=0; i
             
               paths; genPaths(paths, preStrMap, end); return ret; }private: void genPaths(vector
              
               & paths, unordered_map
               
                
                 > &preStrMap, string& curr) { paths.push_back(curr); if (preStrMap[curr].empty()) ret.push_back(vector
                 
                  (paths.rbegin(), paths.rend())); for (auto itr = preStrMap[curr].begin(); itr != preStrMap[curr].end(); ++itr) { genPaths(paths, preStrMap, *itr); } paths.pop_back(); } vector
                  
                   
                    > ret;};
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

然后用了两个unordered_set容器来保存，轻松通过。

class Solution {public:    vector
      
       
        > findLadders(string start, string end, unordered_set
        
          &dict) {        if (dict.empty())            return ret;        //Use unordered_set to implement bfs operation        unordered_set
         
           q1, q2;        unordered_map
          
           > preStrMap;        q1.insert(start);        dict.erase(start);        while (true) {            for (USS_CITR itr=q1.begin(); itr!=q1.end(); ++itr) {                string str = *itr;                for (int i=0; i
           
             paths; genPaths(paths, preStrMap, end); return ret; }private: typedef unordered_set
            
             ::const_iterator USS_CITR; void genPaths(vector
             
              & paths, unordered_map
              
               
                > &preStrMap, string& curr) { paths.push_back(curr); if (preStrMap[curr].empty()) ret.push_back(vector
                
                 (paths.rbegin(), paths.rend())); for (auto itr = preStrMap[curr].begin(); itr != preStrMap[curr].end(); ++itr) { genPaths(paths, preStrMap, *itr); } paths.pop_back(); } vector
                 
                  
                   > ret;};