127. 单词接龙/C++_简单单词接龙 c++

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    int L = beginWord.size();
    unordered_map<string,vector<string>> map;
    
    for(string str:wordList){
        for(int i=0;i<L;++i){
            string strNew = str.substr(0,i)+"*"+str.substr(i+1);
            auto it = map.find(strNew);
            if(it!=map.end())
                map[strNew].push_back(str);
            else
                map[strNew]=vector<string>{str};
        }
    }
    
    queue<pair<string,int>> que;
    que.push(make_pair(beginWord,1));
    
    unordered_map<string,bool> visited;
    visited[beginWord]=true;
    
    while(!que.empty()){
        auto node = que.front();
        que.pop();
        string str = node.first;
        int level = node.second;
        
        for(int i=0;i<L;++i){
            string strNew = str.substr(0,i)+"*"+str.substr(i+1);
            vector<string> vec = map[strNew];
            
            for(auto s:vec){
                if(s==endWord)
                    return level+1;
                if(visited.find(s)==visited.end()){
                    visited[s]=true;
                    que.push(make_pair(s,level+1));
                }
            }
        }
    }
    return 0;
}
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