目录

0127:单词接龙(★★)

力扣第 127 题

题目

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

  • 每一对相邻的单词只差一个字母。
  • 对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。
  • sk == endWord

给你两个单词 beginWord endWord 和一个字典 wordList ,返回 beginWordendWord最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 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
  • beginWordendWordwordList[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