Leetcode.127 单词接龙

题目链接

Leetcode.127 单词接龙 hard

题目描述

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

• 每一对相邻的单词只差一个字母。
• 对于 $1\le i\le k$ 时，每个 $s_i$ 都在 wordList中。注意， beginWord不需要在 wordList中。
• $s_k=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中的所有字符串 互不相同

分析：

由于是求 最短序列，所以可以使用BFS（BFS 可以求最短路）。

先用一个哈希表记录单词表中的所有单词。

用一个队列 q ，先将beginWord入队，然后开始BFS，并用一个 ans 记录最短序列长度。如果中途能够达到 endWord就返回最短序列长度，否则返回 0。

时间复杂度：$O(26m\ast n^2)$

代码：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //用一个哈希表记录所有的单词
        unordered_set<string> uset;
        for(auto &s:wordList) uset.insert(s);

        //如果结尾单词 不在哈希表里 说明beginword 无法转换为 endword 返回0
        if(!uset.count(endWord)) return 0;

        //队列 进行bfs
        queue<string> q;
        q.push(beginWord);

        //记录最短序列长度
        int ans = 0;
        while(!q.empty()){
            int sz = q.size();
            for(int i = 0;i < sz;i++){
                //队列首部元素出队
                auto s = q.front();
                q.pop();
                //如果是endword 说明已经达到了终点 直接返回
                if(s == endWord) return ans + 1;
                
                //查找uset中 是否还有能被此时的 s 转换为的单词
                //s 的每一位字符都要枚举 因为转换规则是 只有一个字符不同 其他都相同的字符串
                int n = s.size();
                for(int i = 0;i < n;i++){
                //记录原始位置的字符 操作结束之后要变回去
                    char op = s[i];
                    for(char c = 'a';c <= 'z';c++){
                        //与 原字符op 相同就跳过 否则才修改进行查找
                        if(op == c) continue;
                        s[i] = c;
                        //如果 uset中有这样的字符 说明原字符串 s 可以转换为 新的字符串 s'                  
                        //就将此时的 s' 入队，并且uset删除此时的 s'
                        if(uset.count(s)){
                             q.push(s);
                             uset.erase(s);
                        }
                    }
                    //恢复现场
                    s[i] = op;
                } 
            }
            ans++;
        }
        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