题目

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

  1. 每次转换只能改变一个字母。
  2. 转换过程中的中间单词必须是字典中的单词。

示例 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” 不在字典中，所以无法进行转换。

说明:

  • 如果不存在这样的转换序列，返回 0。
  • 所有单词具有相同的长度。
  • 所有单词只由小写字母组成。
  • 字典中不存在重复的单词。

  • 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

    方案

    1. class Solution:
    2.   def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
    3.       # 将问题抽象在一个无向无权图中，每个单词作为节点，差距只有一个字母的两个单词之间连一条边。
    4.       # 问题变成找到从起点到终点的最短路径，如果存在的话。
    5.       if endWord not in wordList or not endWord or not beginWord or not wordList:
    6.           return 0
    8.       # 使用临接表建图，比如对第一个单词 hot -> {"*ot": ["hot"], "h*t": ["hot"], "ho*": ["hot"]}
    9.       adj = collections.defaultdict(list)
    10.       for word in wordList:
    11.           for each in self.onestep(word):
    12.               adj[each].append(word)
    14.       # 广度优先搜索
    15.       deque = collections.deque([(beginWord, 1)])
    16.       visited = {beginWord}
    17.       while deque:
    18.           word, ans = deque.popleft()
    19.           for each in self.onestep(word):
    20.               # 找到一步可以转换的单词
    21.               for nextWord in adj[each]:
    22.                   if nextWord == endWord:
    23.                       return ans + 1
    24.                   if nextWord not in visited:
    25.                       deque.append((nextWord, ans+1))
    26.                       visited.add(nextWord)
    27.       return 0
    29.   def onestep(self, word):
    30.       # hot -> "*ot", "h*t""ho*"
    31.       for i in range(len(word)):
    32.           yield word[:i] + "*" + word[i+1:]

  • 注意看题，要求求的是最短转换序列的长度，所以在广度优先搜索时与之前不同；

  • 双向广度优先搜索可以了解下，之前也见到过类似的处理方案。

    原文

    https://leetcode-cn.com/explore/interview/card/2020-top-interview-questions/288/graph/1288/
    https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode/