LeetCode 127. 单词接龙（C++）*_单词接龙c++

思路：
1.如果采用回溯法来的话会超时；
2.这里采用构造图和广度优先遍历结合来实现；首先要构造图，需要将每个字符串对应一个数字id，然后边的构造使用矩阵来实现，这里采用将每一个字符串的id连接每个将该字符串的其中一个字符改为未知字符的字符串的id；如：

对于单词 hit，我们创建三个虚拟节点 *it、h*t、hi*，这三个点都与hit有连接边；
1

以此来判断一个字符串改变一个字符能够到达的点
在广度优先遍历中，如果能够找到一条到达endid的路径，那么该路径就是最短路径。
原题链接：https://leetcode.cn/problems/word-ladder/?favorite=2ckc81c

1.题目如下：

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
1
2

解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
1
2

解释：endWord “cog” 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

2.代码如下：

class Solution {
public:
//思路一：使用广度优先遍历BFS；
/*
    遍历所有可能的路径，只要有路径，那就一定是最短路径；
    同时需要标记每个节点是否被遍历过防止无限重复遍历；可能会超时
*/

//思路二：构造图+广度优先遍历
/*
    将每个字符串转化成节点，并构造同其他节点的边
*/  
    int id=0;
    //创建一个从字符串到id的映射表
    unordered_map<string,int> mapTemp;
    //矩阵用来存储每个结点的id能到达的边
    vector<vector<int>> border;
    void addWord(string& word) {
        if (!mapTemp.count(word)) {
            mapTemp[word] = id++;
            border.emplace_back();
        }
    }
    void addEdge(string& word) {
        addWord(word);
        // 原字符的id
        int id1 = mapTemp[word];
        //将每个字符都逐一变成'*'再放入字典，并构造边界
        //对于单词 hit，我们创建三个虚拟节点 *it、h*t、hi*，这三个点都与hit有连接边
        //让 hit 向这三个虚拟节点分别在矩阵中的id连一条边即可
        for (char& it : word) {
            char tmp = it;
            it = '*';
            // 将*it、h*t、hi*、的id添加进map
            addWord(word);
            // *it、h*t、hi*、的id与原id建立连接
            int id2 =mapTemp[word];
            border[id1].push_back(id2);
            border[id2].push_back(id1);
            it = tmp;
        }
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 如果该字符串不存在，返回0
        if(find(wordList.begin(),wordList.end(),endWord)==wordList.end()){
            return 0;
        }
        // 将每个单词的id及对应边添加进矩阵中
        for (string& word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        // 如果没有该字符串，返回0
        if (!mapTemp.count(endWord)) {
            return 0;
        }
        vector<int> dis(id, INT_MAX);
        // 开始id和结尾id
        int beginId = mapTemp[beginWord], endId = mapTemp[endWord];
        //dis数据记录的是beginid到其他id的距离
        dis[beginId] = 0;

        //队列存储,广度优先遍历
        queue<int> que;
        //从开始单词的id开始，遍历所有边
        que.push(beginId);
        //广度优先遍历
        while (!que.empty()) {
            int x = que.front();
            que.pop();
            if(x==endId) {
                //因为我们使用的是虚拟节点，所以距离要/2；因为每一次遍历，无向边都会导致dis[id]加两次
                //得到的是最短距离
                return dis[endId]/2+1;
            }
            //遍历所有边
            for(int& it:border[x]) {
                if(dis[it] == INT_MAX){
                    dis[it] = dis[x] + 1;
                    que.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
79
80
81
82
83
84
85
86