题目描述

题目链接

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

示例 1：

1
2
3
4
5
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

1
2
3
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

算法1

(抽象 + 爆搜) $O(26nL^2)$ 或 $O(n^2L)$

将题目抽象化，可以看作从起始点开始，每次行走1的距离(对应每次改变单词中一个字母)，求从起点到终点的最短路径(对应从初始单词到结尾单词的最短转换路径)

那么，这个问题可以抽象称为一个边权为1的最短路问题，是一个图论问题

针对这个问题，那么我们可以按照图论问题中求解最短路的方案，逐步解决这个问题

  • 建图
    首先需要将问题构建成为一张图，此处建图有两种方案
    • 依次枚举起始单词的每一位，再枚举每一位能够转换成为的字母，这样能够得到其实单词每转换一个字母所能得到的所有单词
    • 依次枚举单词列表中所有的单词(对应图论中枚举所有的点)，判断当前单词是否可以经过依次变换之后称为枚举的单词，如果成立，说明可以经过一次转换得到该单词(两点之间可以有一条连线)
  • 连边
    • 根据建立的图，开始进行图的遍历，找出每个点距离起点的距离，即需要变更的次数
  • 找到终点
    • 在遍历过程中，找到终时，终点与起点的距离就是两个单词之间需要转换的最少次数

抽象为图论模型之后，可以很容易的得到从起始单词到结束单词的变更次数，但若要找到相应的最短变更序列，还需要从结尾单词开始进行一次dfs，直到起始单词为止，中间经历过的所有单词就是单词转换序列

需要注意的是，在进行dfs时，可以进行剪枝，每当新枚举的单词不在图中，或者距离不合规之后，那么就可以剪枝

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
class Solution {
public:

    string start;
    unordered_map<string, int> dist;
    unordered_set<string> s;
    queue<string> q;
    vector<vector<string>> res;
    vector<string> path;

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        start = beginWord;
        dist[start] = 0;

        for(auto word : wordList) s.insert(word);
        q.push(start);

        while( q.size())
        {
            auto t = q.front();
            q.pop();

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

        if( dist.count(endWord) == 0) return res;
        path.push_back(endWord);
        dfs(endWord);
        return res;
    }

    void dfs(string t)
    {
        if( t == start)
        {
            reverse(path.begin(), path.end());
            res.push_back(path);
            reverse(path.begin(), path.end());
        }
        else
        {
            string r = t;
            for(int i = 0; i < t.size(); i ++)
            {
                t = r;
                for(char j = 'a'; j <= 'z'; j ++)
                {
                    t[i] = j;
                    if( dist.count(t) && dist[t] + 1 == dist[r])
                    {
                        path.push_back(t);
                        dfs(t);
                        path.pop_back();
                    }
                }
            }
        }
    }
};