力扣刷题记录162.1-----127. 单词接龙

---

一、题目

二、代码

class Solution 
{
public:
    //广度优先搜索
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        int i,j;
        //将vector转换成unordered_st 提高查询速度  目前理解不深
        unordered_set<string> wordSet(wordList.begin(),wordList.end());

        //不存在直接返回
        if(wordSet.find(endWord)==wordSet.end()) return 0;

        unordered_map<string,int> visitMap;  //map中存放  当前的word和经过的路径长度

        //初始化队列
        queue<string> que;
        que.push(beginWord); //第一个元素

        //初始化visitMap
        visitMap.insert(pair<string,int>(beginWord,1));

        while(!que.empty())   //本题BSP 核心是队列  存储用unordered_map
        {

            string word=que.front();
            que.pop();
            int path=visitMap[word];
            for(i=0;i<word.size();i++)
            {
                string new_word=word;
                for(j=0;j<26;j++)
                {
                    new_word[i]=j+'a';
                    if(new_word==endWord) return path+1;
                    if(wordSet.find(new_word)!=wordSet.end()&&
                        visitMap.find(new_word)==visitMap.end())
                    {
                        visitMap.insert(pair<string,int>(new_word,path+1));
                        que.push(new_word);
                    }    
                   
                }
            }

        }       



        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
44
45
46
47
48
49
50
51
52

三、运行结果