0127：单词接龙（★★）

力扣第 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 中的所有字符串 互不相同

相似问题：

• 0126：单词接龙 II
• 0433：最小基因变化
• 2452：距离字典两次编辑以内的单词（1459 分）

分析

• 找最短容易想到用 bfs，每轮搜索能转换的单词即可
• 搜索可以用 0676 的方法加速
  • 将单词的某一位改为 ‘.’ 作为单词的 key
  • 每个单词按所有的 key 存在哈希表中
  • 搜索时，取所有 key 对应的列表即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

@cache
def gen(w):
    return [w[:i]+'*'+w[i+1:] for i in range(len(w))]
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        d = defaultdict(list)
        for w in wordList:
            for key in gen(w):
                d[key].append(w)
        Q, vis = deque([(beginWord,1)]), {beginWord}
        while Q:
            u,w = Q.popleft()
            if u==endWord:
                return w
            for key in gen(u):
                for v in d[key]:
                    if v not in vis:
                        vis.add(v)
                        Q.append((v,w+1))
        return 0

83 ms