LC

单词接龙
单词接龙 II

思路

这个题属于表面看和图论毫无关联，但本质上就是图论的题目（我记得第一次看到这题是在舍友的求职笔试上……）

把每个单词看作结点，如果一个单词能够只改变一个字母变成另外一个单词，那么它们之间就存在一条权值为1的边。问的是最短操作次数，实际上就是求边权为1的最短路。直接用BFS即可。

至于进阶版，需要记录路径。在BFS做完之后，实际上除了求出最短距离之外，我们也建好了图。每个结点都对应一个距离，表示到起点的最短距离。如何找到最优解的路径呢？很简单，只要下一个单词到起点的距离和当前结点到起点的距离差1，就说明这个点在最优路径上（因为在BFS的时候是不断+1直到终点的嘛）

建图方式的选择

有2种建图方式，选哪一种比较快取决于n和L的大小，n是字典大小，L是单词长度。

  1. 两两枚举所有单词（包括开始单词）。判断能否转移。时间复杂度$O(n^2L)$
  2. 枚举所有单词，然后枚举每个单词所有位上的字母（共26个字母），判断这个单词是否存在（判断是否存在是字符串哈希问题，$O(L)$）。时间复杂度$O(26nL^2)$

当$n > 26L$的时候，选第2种。否则选第一种。根据Leetcode的数据，这题要用第2种方式建图。

时间复杂度

主要有以下3个部分：

  1. 建图 $O(26nL^2)$
  2. BFS 所有点只遍历一次，遍历每个点时需要哈希 $O(nL)$
  3. DFS 总方案数是指数级的，记录方案需要$O(nL)$ 所以总的时间为$O(2^nnL)$

因此总时间复杂度为：$O(26nL^2) + O(nL) + O(2^nnL) = O(2^nnL)$

单词接龙 代码

class Solution {
public:
    unordered_map<string, int> dist;
    unordered_set<string> S;

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for(auto &word : wordList) S.insert(word);
        queue<string> q;
        q.push(beginWord);
        dist[beginWord] = 0;

        while(q.size()) {
            string top = q.front();
            q.pop();

            string t = top;
            for(int i = 0; i < top.size(); i++) {
                t = top;
                for(char j = 'a'; j <= 'z'; j++) {
                    t[i] = j;
                    if(t != top && S.count(t) && dist.count(t) == 0) {
                        dist[t] = dist[top] + 1;
                        if(t == endWord) break;
                        q.push(t);
                    }
                }
            }
        }

        return dist[endWord] == 0 ? 0 : dist[endWord] + 1;
    }
};

单词接龙II 代码

class Solution {
public:
    unordered_map<string, int> dist;
    unordered_set<string> S;
    vector<vector<string>> ans;
    vector<string> path;

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        for(auto &word: wordList) S.insert(word);
        queue<string> q;
        q.push(beginWord);

        while(q.size()) {
            string top = q.front();
            q.pop();

            string t = top;
            for(int i = 0; i < top.size(); i++) {
                t = top;
                for(char j = 'a'; j <= 'z'; j++) {
                    t[i] = j;
                    if(S.count(t) && dist.count(t) == 0 && t != top) {
                        dist[t] = dist[top] + 1;
                        if(t == endWord) break;
                        q.push(t);
                    }
                }
            }
        }

        if(dist.count(endWord)) {
            path.push_back(beginWord);
            dfs(beginWord, endWord);
        }
        return ans;
    }

    void dfs(string st, string ed) {
        if(st == ed) {
            ans.push_back(path);
            return;
        }

        string t = st;
        for(int i = 0; i < st.size(); i++) {
            t = st;
            for(char j = 'a'; j <= 'z'; j++) {
                t[i] = j;
                if(t != st && dist.count(t) && dist[t] == dist[st] + 1) {
                    path.push_back(t);
                    dfs(t, ed);
                    path.pop_back();
                }
            }
        }
    }

};