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

分析

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

解答

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

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

119 ms