127. 单词接龙【 力扣(LeetCode) 】

零、原题链接

127. 单词接龙

一、题目描述

字典 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
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：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 中的所有字符串 互不相同

三、解题思路

  这题和 433. 最小基因变化 基本思路是一样的，区别就在于单词的长度不固定，单词的字母范围不一样。本质上都是构图+BFS 找最短路径。有下面两种方案：

1. 正向搜索：从起点一直搜索到终点
2. 双向搜索：从起点和终点一直搜索到相交的点

虽然复杂度相同，但是双向搜索的复杂度的系数会小一点。

3.1 BFS

1. 编写计算两个单词的变化次数的函数。
2. 初始化：将起点及其相邻元素入队，并寻找终点
3. 构图：根据 wordList 里面的单词进行构图，只要两个单词字母变化次数小于等于 1 ，就表示这两个单词相邻。
4. BFS：弹出队首元素，判断是否为终点，是则返回步数；不是，则将其邻居（未被访问过）加入搜索队列。

3.2 BFS(双向搜索）

1. 编写计算两个单词的变化次数的函数。
2. 初始化：将起点及其相邻元素入队，并寻找终点。【与 3.1 不同的是，vis 向量表示不一样，>0 表示正向搜索的步长，<0 表示反向搜索的步长，=0 表示未搜索。】
3. 构图：根据 wordList 里面的单词进行构图，只要两个单词字母变化次数小于等于 1 ，就表示这两个单词相邻。
4. BFS：弹出队首元素，判断是否为终点，是则返回步数；不是，则将其邻居（未被访问过）加入搜索队列。【与 3.1 不同的是，这里要考虑正向搜索到反向相交点，反向搜索到正向相交点 和 未搜索的情况。】

四、参考代码

4.1 BFS

时间复杂度：$\mathrm{O}(C{N}^2)$【C 是单词长度，N 是单词个数】
空间复杂度：$\mathrm{O}(C{N}^2)$

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int n = wordList.size();
        vector<vector<bool>> adjMatrix(n, vector<bool>(n, false));
        vector<bool> vis(n, false);

        auto change = [&](const string& a, const string& b) {
            int count = 0;
            for (int i = 0; i < a.size(); i++) {
                if (a[i] != b[i])
                    count++;
            }
            return count;
        };

        // 初始化
        vector<pair<int, int>> bfs(n + 1);
        int l = 0, r = 0, end = -1;
        for (int i = 0; i < n; i++) {
            if (change(wordList[i], beginWord) <= 1) {
                bfs[r++] = make_pair(i, 2);
                vis[i] = true;
            }

            if (change(wordList[i], endWord) == 0)
                end = i;
        }
        if (end == -1)
            return 0;

        // 构图
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (change(wordList[i], wordList[j]) > 1)
                    continue;
                adjMatrix[i][j] = adjMatrix[j][i] = true;
            }
        }

        // BFS
        while (l < r) {
            auto item = bfs[l++];
            if (item.first == end)
                return item.second;

            // 添加其邻居
            for (int i = 0; i < n; i++) {
                if (vis[i] || !adjMatrix[item.first][i])
                    continue;
                vis[i] = true;
                bfs[r++] = make_pair(i, item.second + 1);
            }
        }

        return 0;
    }
};

4.2 BFS（双向搜索）

时间复杂度：$\mathrm{O}(C{N}^2)$【C 是单词长度，N 是单词个数】
空间复杂度：$\mathrm{O}(C{N}^2)$

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int n = wordList.size();
        vector<vector<bool>> adjMatrix(n, vector<bool>(n, false));
        vector<int> vis(n, 0);
        vector<int> bfs(n + 1);

        auto change = [&](const string& a, const string& b) {
            int count = 0;
            for (int i = 0; i < a.size(); i++) {
                if (a[i] != b[i])
                    count++;
            }
            return count;
        };

        // 初始化
        int l = 0, r = 0, end = -1, t;
        for (int i = 0; i < n; i++) {
            t = change(wordList[i], beginWord);
            if (t <= 1) {
                bfs[r++] = i;
                vis[i] = t + 1;
            }

            if (change(wordList[i], endWord) == 0) {
                end = i;
            }
        }
        if (end == -1) // 终点不存在
            return 0;
        if (vis[end] > 0) // 终点在正向搜索就找到了
            return vis[end];
        bfs[r++] = end;
        vis[end] = -1;

        // 构图
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (change(wordList[i], wordList[j]) > 1)
                    continue;
                adjMatrix[i][j] = adjMatrix[j][i] = true;
            }
        }

        // BFS
        while (l < r) {
            auto item = bfs[l++];

            // 添加其邻居
            for (int i = 0; i < n; i++) {
                if (!adjMatrix[item][i])
                    continue;
                if (vis[i] > 0 && vis[item] < 0) { // 反向搜索到正向相交
                    return vis[i] - vis[item];
                } else if (vis[i] < 0 && vis[item] > 0) { // 正向搜索到反向相交
                    return vis[item] - vis[i];
                } else if (vis[i] == 0) { // 未搜索
                    bfs[r++] = i;
                    vis[i] = vis[item] > 0 ? vis[item] + 1 : vis[item] - 1;
                }
            }
        }

        return 0;
    }
};