题目描述

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

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

说明

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

样例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

(宽度优先搜索) $O(n^2)$

本问题可以转化成一个图论问题，将每个单词看成点，如果两个单词直接可以互相转换，那么就在两点之间连一条边，距离为1。由于本题需要找到最短的转换序列，而在距离都是1的情况下我们可以直接用宽搜来做。

我们从起点beginWord开始，枚举下一层可能的节点，直到遇到终点endWord为止。这里用了vis数组判重，从起点到每个节点的距离记录在队列里。

我们也可以去掉vis数组，新开一个dist数组记录起点到该点的距离，并且可以利用这个dist数组判重，因为宽搜的特性每个点只会被访问一次并且第一次访问的时候就是起点到该点距离的最小值，dist数组值未被赋过说明还未访问到该点，有值说明已经被访问过。

时间复杂度

共有 $n$ 个单词，每次枚举下一层的时候我们需要遍历所有还没有走过的点，共需要判断 $O(n^2)$ 次。而每次判断需要将每个单词遍历一遍，所以总复杂度为 $O(n^2L)$，这里 $L$ 是单词的长度。

C++ 代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        queue<pair<string, int>> q;
        q.push({beginWord, 1});

        int n = wordList.size();
        vector<bool> vis(n, false);
        while (q.size()) {
            auto t = q.front();
            q.pop();
            if (t.first == endWord) return t.second;

            for (int i = 0; i < n; i ++ ) {
                if (!vis[i] && check(t.first, wordList[i])) {
                    q.push({wordList[i], t.second + 1});
                    vis[i] = true;
                }
            }
        }
        return 0;
    }

    bool check(string &s, string &t) {
        int cnt = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (s[i] != t[i]) cnt ++ ;
        }
        return cnt == 1;
    }
};

算法2

(双向广搜+哈希) $O(\sqrt{n}L^2)\sim O(nL^2)$

因为起点和终点都已知，所以我们可以用双向广搜来节省时间和空间，即同时从起点和终点开始进行宽搜。假如在中间点相遇，那么两边走的步数分别为 $\frac{d}{2}$，假设每个节点分支数为 $b$，那么时间和空间都是 $2\times b^{\frac{d}{2}}$，比朴素的做法 $b^d$ 要节省很多。

并且由于单词的长度都是一样的而且只由小写字母组成，我们可以暴力枚举单词的每个字母，看变化后的单词是否存在于单词列表wordList中，这可以利用哈希表在 $O(L)$ 的时间内做到，因此每次枚举下一层节点的复杂度由 $O(nL)$ 变成了 $O(26L * L) = O(L^2)$，总时间复杂度由 $O(n^2L)$ 变成了 $O(nL^2)$。

为了简化代码，这里并不是严格的从两头交替的走，而是每次从当前层中节点数较少的那一头走。由于这里每走一步会将该层所有节点全部拓展完，所以可以用一个变量res来记录步数，并且这里用两个哈希表来充当可以判重的队列。

时间复杂度

在最优的情况下两个宽搜在中间点相遇，设每个节点分支数为 $b$，则一共会有 $\log_bn$ 层，即单向宽搜从起点到终点需要走 $\log_bn$ 步。那么双向宽搜只需要 $\frac{\log_bn}{2}$步，路上的节点数为 $b^\frac{\log_bn}{2} = \sqrt{n}$，总时间复杂度为 $O(2 * \sqrt{n}L^2) = O(\sqrt{n}L^2)$。

在最坏情况下从起点到终点需要 $n$ 步，即分枝数为1，此时双向宽搜与单向宽搜时间复杂度相同，都为 $O(nL^2)$。

C++ 代码

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        if (!hash.count(endWord)) return 0;
        unordered_set<string> head, tail;
        head.insert(beginWord), tail.insert(endWord);

        int res = 2;
        while (head.size() && tail.size()) {
            if (head.size() > tail.size()) {
                swap(head, tail);
            }

            unordered_set<string> tmp;
            for (auto word : head) {
                for (int i = 0; i < word.size(); i ++ ) {
                    char c = word[i];
                    for (int j = 0; j < 26; j ++ ) {
                        if ('a' + j == c) continue;
                        word[i] = 'a' + j;
                        if (tail.count(word)) return res;
                        if (hash.count(word)) {
                            tmp.insert(word);
                            hash.erase(word);
                        }
                    }
                    word[i] = c;
                }  
            }
            res ++ ;
            swap(head, tmp);
        }
        return 0;
    }
};