LeetCode每日一题--127.单词接龙（广度优先搜索）_广度优先搜索汉字接龙

题目：跳转至 127.单词接龙
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设
  beginWord 和 endWord 是非空的，且二者不相同。

class Solution {
public:   	
	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            
        }
};
1
2
3
4
5
6

思路：
广度优先搜素，先把beginWord加入队列，队列不为空时，取队首单词在wordList中寻找转换有效且未被访问过的单词加入队列，循环直至找到endWord。

class Solution {
public:
    bool IsValidTrans(string a,string b){  //是否只改动一个字符
        int count=0;
        for(int i=0;i<a.length();++i){
            if(a[i]!=b[i])
                ++count;
        }
        if(count==1)
            return true;
        return false;
    }
    bool IsnotVisited(vector<string>& VisitedList,string s){  //是否访问过
        for(auto x:VisitedList){
            if(x==s)
                return false;
        }
        VisitedList.push_back(s);  //没有访问过就加入
        return true;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int len=wordList.size();
        queue<string> que;
        que.push(beginWord);
        int sum=0;
        vector<string> VisitedList;
        while(!que.empty()){
            string tmp=que.front();
            que.pop();
            for(auto x:wordList){
                if(IsValidTrans(x,tmp) && IsnotVisited(VisitedList,x)){//转换有效且没有被访问过
                    que.push(x);
                    if(x==endWord)
                        return sum+1;
                }
            }
            ++sum;
        }
        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

上述给出的最短距离是不准的，因为最短距离是直接计算了入列后的单词挨个出列的个数，举例：
hit->hot hig->cot got hog->…
得出的结果就是1+2+3+…
修改增加一层循环，把最短距离计数放在循环外，使得每次改动一次之后的单词不会额外触发计数的增加，上述结果也成为1+1+1+…

class Solution {
public:
    bool IsValidTrans(string a,string b){  //是否只改动一个字符
        int count=0;
        for(int i=0;i<a.length();++i){
            if(a[i]!=b[i])
                ++count;
        }
        if(count==1)
            return true;
        return false;
    }
    bool IsnotVisited(vector<string>& VisitedList,string s){  //是否访问过
        for(auto x:VisitedList){
            if(x==s)
                return false;
        }
        VisitedList.push_back(s);  //没有访问过就加入
        return true;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int len=wordList.size();
        queue<string> que;
        que.push(beginWord);
        int sum=1;
        vector<string> VisitedList;
        while(!que.empty()){
            int i=0;
            int len=que.size();
            while(i++<len){  //方便计数，把每一个单词单个变动一次的所有结果都循环完成
                string tmp=que.front();
                que.pop();
                for(auto x:wordList){
                    if(IsValidTrans(x,tmp) && IsnotVisited(VisitedList,x)){//转换有效且没有被访问过
                        que.push(x);
                        if(x==endWord)
                            return sum+1;
                    }
                }
            }
            ++sum;
        }
        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

结果正确但运行超时。开始抄答案（咳，学习），下面放官方题解
双向广度优先搜索：
借用从beginWord到endWord，和endWord到beginWord两个同时进行的广度搜索每次各扩展一层节点，当beginWord存在一个节点在存储从endWord扩展的距离数组中有值（或者相反）时，就找到了最短路径，停止搜索。

class Solution {
public:
    unordered_map<string,int> wordId;  //哈希表存储单词和单词对应序号
    vector<vector<int>> edge;  //二维数据作邻接列表
    int nodeNum=0;  //哈希表存放的单词的首位序号由0开始

    void addWord(string& word){
        if(!wordId.count(word)){  //计算word是否在wordId中
            wordId[word]=nodeNum++;  //如果在，当前nodeNum给他并nodeNum加1，即给每个单词标号
            edge.emplace_back();  //同时增加一条边
        }
    }

    void addEdge(string& word){
        addWord(word);
        int id1=wordId[word];  //获取word对应的标号
        for(char& it:word){
            char tmp=it;  //对单词的每一个字符换成 * 成为虚拟节点，加入哈希表wordID并得到一个对应序号
            it='*';
            addWord(word);
            int id2=wordId[word];  //获取变动一个字符的单词的序号
            edge[id1].push_back(id2);  //二维数组（邻接矩阵）存储边的信息，即x两个单词间的转换有效
            edge[id2].push_back(id1);
            it=tmp;   //还原单词
        }
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for(string& word:wordList)  //建图，对每一个单词枚举可能的虚拟节点并通过edge连接对应的序号
            addEdge(word);
        addEdge(beginWord);  //并放入beginWord
        if(!wordId.count(endWord))  //如果endWord不在给出的字典内，不可能接龙成功
            return 0;

        vector<int> disBegin(nodeNum,INT_MAX);  //创建nodeNum大小的数组并初始化最大值，统计转换到每个标号的单词所需要的步数
        int beginId=wordId[beginWord];  //获取beginWord对应的标号
        disBegin[beginId]=0;  //距离从0开始计数
        queue<int> queBegin;  //创建从beginWord开始扩展的队列，存入对应标号
        queBegin.push(beginId);

        vector<int> disEnd(nodeNum,INT_MAX);  //创建nodeNum大小的数组并初始化最大值，统计转换到每个标号的单词所需要的步数
        int endId=wordId[endWord];  //获取endWord对应的标号
        disEnd[endId]=0;   //距离从0开始计数
        queue<int> queEnd;  //创建从beginWord开始扩展的队列，存入对应标号
        queEnd.push(endId);

        while(!queBegin.empty() && !queEnd.empty()){  //当两个队列均不为空时
            int queBeginSize=queBegin.size();
            for(int i=0;i<queBeginSize;++i){
                int nodeBegin=queBegin.front();  //从beginId往下走，取队首存放的标号
                queBegin.pop();
                if(disEnd[nodeBegin]!=INT_MAX)  //在从底往上记录距离的数组中找到从上往下查找的单词，即搜索到终点，因为加了虚拟节点，所以对半除加一
                    return (disBegin[nodeBegin]+disEnd[nodeBegin])/2+1;
                for(int& it:edge[nodeBegin]){  //遍历标号对应的边集，获取能转换成功的单词标号
                    if(disBegin[it]==INT_MAX){  //把能转换成功的单词距离记录到disBegin中，每层（单次能成功变换对应的单词的最短距离数目）加1
                        disBegin[it]=disBegin[nodeBegin]+1;
                        queBegin.push(it);  //加入队列，用于循环查找下一层能成功转换的单词
                    }
                }
            }

            int queEndSize=queEnd.size();
            for(int i=0;i<queEndSize;++i){
                int nodeEnd=queEnd.front();  //从endId往上走，取队首存放的标号
                queEnd.pop();
                if(disBegin[nodeEnd]!=INT_MAX)  //同理，搜索到终点
                    return (disBegin[nodeEnd]+disEnd[nodeEnd])/2+1;
                for(int& it:edge[nodeEnd]){  //赋值每层成功转换的最短距离
                    if(disEnd[it]==INT_MAX){
                        disEnd[it]=disEnd[nodeEnd]+1;
                        queEnd.push(it);
                    }
                }
            }
        }
        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
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

（代码太长默认浏览器一复制过来就卡页面，换了谷歌能显示全就很优秀）