Leetcode 126. Word Ladder II

Posted on | In |

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:

Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:

beginWord = “hit”,

endWord = “cog”,

wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output:
[

[“hit”,”hot”,”dot”,”dog”,”cog”],

[“hit”,”hot”,”lot”,”log”,”cog”]

]
Example 2:

Input:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: []

Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class Solution {
public:
     unordered_map<string,vector<string>> parents;
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        queue<string> q;
             vector<vector<string>> ans;
        unordered_set<string> dict(wordList.begin(),wordList.end());
        if(!dict.count(endWord)) return ans;
        dict.erase(beginWord);
        dict.erase(endWord);
        unordered_map<string,int> step{{beginWord,1}};//,
        q.push(beginWord);
        bool find=false;
         int steps=0;
        while(!q.empty()&&!find){
            steps++;
           for(int size=q.size();size>0;size--){     //!!
            //for(int size=0;size<t;size++){ 
                //不能写成下面的形式 q弹出来一个元素 queue的size变化了 要么就是在弹出元素前 记录下当前这一层队列的长度
            string p=q.front();
            q.pop();
            string w=p;   
                //w是P要扩展的节点
            for(int i=0;i<p.length();i++){
                 char ch=w[i];
                for(int j=0;j<26;j++){
                    if('a'+j==ch) continue;//!!
                    w[i]='a'+j;
                    if(w==endWord) {
                      parents[w].push_back(p);
                        find=true;         
                    }
                    else{
                                       
                      //  if(step.count(w)&&step.at(p)<step[w]){
                         if (step.count(w) && steps < step.at(w)){
                             parents[w].push_back(p);
                         } 
                             
                           
                        }
                        if(!dict.count(w)) continue;     
                           parents[w].push_back(p);
                            dict.erase(w);//!!
                            step[w]=step.at(p)+1;
                            q.push(w);    
                    }
                     w[i]=ch;
                }    
            }
            
          }  
        
 
             vector<string> curr{endWord};
   
     if(find)                                       
        printpath(beginWord, endWord,curr,ans);

     
       
        return ans;
        
        
        
        }
        

  //加引用！！ curr vector 每次调用 增加一个word  每个curr是个可行解
    
        void printpath(string &beginWord, string &endWord,vector<string> &curr,vector<vector<string>> &ans){
          if(endWord==beginWord) {
              ans.push_back(vector<string>(curr.rbegin(),curr.rend()));
               return ;
                
          }
            for(int i=0;i<parents[endWord].size();i++){
                curr.push_back(parents.at(endWord).at(i));//!!
                printpath(beginWord,parents.at(endWord).at(i),curr,ans);
                curr.pop_back();
                
            }
            
            
            
        }
    
    
    
};

补充 下标访问容器和调用at访问的区别

1
2
3
4
5
6
7
8
9
10
11
#include<iostream> 
#include<unordered_map>
#include<string>
using namespace std;
//map 用下标访问如果键不存在 会创建 一个空对象
//用at 访问 如果键不存在 会抛出一个异常 
int main(){
	unordered_map<string,int> m{{"1",2}};
//	cout<<m["2"]<<endl;
cout<<m.at("2")<<endl;	
}