Word Ladder
你会得到两个单词：beginWord 和 endWord，以及一个单词列表 wordList。变换序列以 beginWord 开始，以 endWord 结束，并且从一个单词到下一个单词时，恰好改变一个字母。beginWord 之后的每个单词都必须来自 wordList，因此 endWord 必须在其中；beginWord 则不一定要在其中。
返回最短变换序列中的单词数，包括两端的单词。如果不存在这样的序列，则返回 0。
函数
- beginWordstring
- 阶梯的第一个单词
- endWordstring
- 梯子必须到达的单词
- wordListstring-array
- 之后每一步都必须来自的单词
- 返回值integer
- 最短阶梯中的单词数，如果不存在则为 0
约束条件
1 ≤ beginWord.length ≤ 10endWord和wordList中的每个单词都与beginWord长度相同。1 ≤ wordList.length ≤ 5000- 所有单词都只包含小写英文字母。
beginWord != endWordwordList中的单词各不相同。beginWord可能是其中一个，也可能不是。
示例
- 输入
- beginWord = "lead"endWord = "gold"wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
- 输出
- 4
- 解释
lead和gold有三个字母不同，因此词语阶梯至少需要 4 个单词，而lead、load、goad、gold正好有 4 个。lend和lewd是死路。
- 输入
- beginWord = "cat"endWord = "dog"wordList = ["cot", "cog", "dot", "dig"]
- 输出
- 0
- 解释
cat、cot、cog只差一个字母就能变成dog，但列表中没有dog，所以没有阶梯能以它结束。
- 输入
- beginWord = "ab"endWord = "cd"wordList = ["ab", "cb", "cd", "ad"]
- 输出
- 3
- 解释
ab、ad、cd和ab、cb、cd都各有 3 个单词。ab也在列表中，但开头只计算一次。
进阶
你能否直接返回一条最短的阶梯，也就是按顺序排列的单词，而不是它的长度？
提示
逐个打开提示，每个都会多透露一点。
把每个单词想象成一个点，再在只相差一个字母的两个单词之间画一条线。在这幅图中，什么是阶梯？最短的阶梯是什么？
最短梯子是线条最少的路径，并且每条线的权重相同。广度优先搜索会先到达所有只需一步就能到达的单词，然后才会到达任何需要两步才能到达的单词，因此第一次到达
endWord时，使用的步数最少。第一次到达一个单词时，就将它标记为已访问。把一个单词和整个列表逐一比较来找出它的邻居，速度很慢。你可以改为每次隐藏一个字母：
hot、hat和hit都会变成h*t。把每个单词放入它的每种模式对应的桶中。一个单词的邻居就是与它处于同一个桶中的其他单词。从beginWord开始逐层搜索，并统计层数。
题解
把单词看作图中的节点，两个单词相差一个字母时，它们之间就有一条边。每条边的代价都相同，因此广度优先搜索可以找到最短的单词梯。难点在于快速找到这些边。下面，n 表示单词数量，L 表示单词长度。
用深度优先搜索尝试每个梯子
结果正确，但无法在最大的测试中运行完毕
思路
从当前单词开始，尝试每个只差一个字母且尚未使用的单词，并继续向下搜索；到达 endWord 时保持单词长度不变。将路径上的单词标记为已使用，回溯时再释放它们。一旦找到由 best 个单词组成的阶梯，就停止扩展由 best-1 个单词组成的路径。
这种方法会尝试所有不重复单词的阶梯，而最短阶梯不会重复单词：删去两个相同单词之间的部分，就能缩短阶梯。
aaa、baa 一直到 zaa 这 26 个单词两两只差一个字母，排列顺序大约有 4 × 10^26 种。如果无法到达 endWord，剪枝条件就永远不会触发，搜索会尝试所有排列。
算法
- 如果
beginWord在列表中，就将其标记为已使用，并将best设为 0。 search(word, length)：到达endWord时，如果length小于best，就保留length，然后返回。如果已设置best，且length + 1 ≥ best，就返回。- 否则，对于每个未使用且只差一个字母的单词，将其标记为已使用，调用
search(next, length + 1)，然后取消标记。 - 调用
search(beginWord, 1)后，返回best。
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
best = 0 # words in the shortest sequence found so far, 0 while there is none
used = [word == beginWord for word in wordList] # words on the current path
def search(word, length):
nonlocal best
if word == endWord:
if best == 0 or length < best:
best = length
return
if best != 0 and length + 1 >= best:
return # any longer path cannot beat the best one
for i, candidate in enumerate(wordList):
if not used[i] and one_letter_apart(word, candidate):
used[i] = True
search(candidate, length + 1)
used[i] = False # free the word for other paths
search(beginWord, 1)
return best广度优先搜索，比较每一对
结果正确，但无法在最大的测试中运行完毕
思路
队列会按距离顺序探索单词：距离为 d 的所有单词都会先于距离为 d + 1 的任何单词离开队列。因此，当一个单词第一次在距离 d 处被找到时，所有距离更近的单词都已经探索过了，而更短的单词梯子也会更早到达它。它加入队列的那一刻，距离就已确定，所以要在此时将它标记为已访问；第一次遇到 endWord 时，它的距离就是答案。
这个版本通过将一个单词与列表中的每个单词进行比较来查找它的邻居，并在发现第二处差异时停止：O(n² × L)，对于 5,000 个单词，最多需要比较 2500 万个单词。
算法
- 如果
endWord不在wordList中，则返回 0。 - 将
beginWord加入队列，长度为 1；如果它在列表中，则标记为已访问。 - 取出下一个单词，并将它与每个未访问的单词进行比较。对于相差一个字母的单词：如果它是
endWord，则返回长度 + 1；否则将它标记为已访问，并以长度 + 1 将它加入队列。 - 如果队列为空，则返回 0。
from collections import deque
def ladderLength(beginWord, endWord, wordList):
def one_letter_apart(a, b):
differences = 0
for x, y in zip(a, b):
if x != y:
differences += 1
if differences > 1:
return False
return differences == 1
if endWord not in wordList:
return 0
visited = [word == beginWord for word in wordList]
queue = deque([(beginWord, 1)]) # (word, words in the sequence up to it)
while queue:
word, length = queue.popleft()
# Compare against every word to find the neighbours.
for i, candidate in enumerate(wordList):
if not visited[i] and one_letter_apart(word, candidate):
if candidate == endWord:
return length + 1
visited[i] = True
queue.append((candidate, length + 1))
return 0使用通配符桶进行广度优先搜索
思路
两个单词恰好相差一个字母，当且仅当隐藏同一位置的字母后，它们会变得相同：hot 和 hit 都会变成 h*t。为每个单词生成 L 个模式，每个隐藏位置对应一个，然后将它添加到每个模式对应的桶中。一个单词的邻居就是它所在的 L 个桶中的其他单词，通过 L 次哈希查找即可找到，无需遍历整个列表。
在第一个示例中，l*ad 包含 load，而 le*d 包含 lend 和 lewd，因此这三个单词位于第 2 层；接着，*oad 会找到 goad，而 go*d 会在第 4 层找到 gold。
扫描一个桶后，其中的每个单词都已被访问，因此要清空这个桶：包含 26 个单词的桶 *aa 只扫描一次，而不是 26 次。时间和空间复杂度均为 O(n × L²)，对于 5,000 个长度为 10 的单词，大约需要处理 500,000 个字母。
算法
- 如果
endWord不在wordList中，返回 0。 - 将每个单词（包括
beginWord）放入它对应的每个L模式桶中。 - 将
beginWord标记为已访问，并以长度 1 将其加入队列。 - 遍历当前层的每个单词：如果是
endWord，就返回长度。否则，将其每个模式桶中所有未访问的单词移到下一层，标记为已访问，并清空该桶。 - 每进入一层，长度加 1。如果队列为空，返回 0。
from collections import defaultdict, deque
def ladderLength(beginWord, endWord, wordList):
if endWord not in wordList:
return 0
size = len(beginWord)
# "h*t" -> every word that matches it: hot, hat, hit... are one letter apart.
buckets = defaultdict(list)
for word in set(wordList) | {beginWord}:
for i in range(size):
buckets[word[:i] + "*" + word[i + 1:]].append(word)
visited = {beginWord}
queue = deque([beginWord])
length = 1 # words in the sequence up to the current level
while queue:
for _ in range(len(queue)): # one level: every word at this distance
word = queue.popleft()
if word == endWord:
return length
for i in range(size):
pattern = word[:i] + "*" + word[i + 1:]
for neighbour in buckets[pattern]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
buckets[pattern] = [] # all of them are visited now: never scan it again
length += 1
return 0
易错点和边界情况
- 数变化次数，而不是单词数。
lead到gold要变化 3 次，共有 4 个单词；答案是 4。 - 漏掉了检查
endWord是否在wordList中。第二个示例会到达cog，它与dog只差一个字母，但答案是 0。 - 等单词出队时才标记为已访问。这样，
*aa这个桶中的单词最多可以入队 25 次，队列会远远超过n。 - 沿着转换阶梯递归。最短转换阶梯可能有几千个单词，足以导致调用栈溢出。
常见问题3
Word Ladder 的时间复杂度是多少？
使用通配符桶时，对于长度为 L 的 n 个单词，时间复杂度为 O(n × L²)：每个单词有 L 个模式，每个模式包含 L 个字母。比较每一对单词的开销为 O(n² × L)，而用深度优先搜索尝试每条单词梯子则会产生指数级开销。
如何找出只差一个字母的单词？
通配符桶是一种方法。另一种方法是将每个位置依次替换为 26 个字母中的每一个，然后在单词的哈希集合中查找结果：每个单词需要进行 26 × L 次查找，每次查找涉及 L 个字母，总复杂度为 O(n × 26 × L²)。这两种方法都比遍历整个列表快。
双向 BFS 能让 Word Ladder 更快吗？
是的。同时从两端开始搜索，每次让较小的一侧扩展一层，两侧相遇时停止。每个单词大约有 b 个邻居，变化 d 次时，一次搜索可能会触及约 b^d 个单词；两次搜索从中间相遇时，可能会触及约 2 × b^(d/2) 个单词。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def ladderLength(beginWord, endWord, wordList):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
beginWord = "lead" endWord = "gold" wordList = ["load", "goad", "gold", "lend", "lewd", "bold"]
预期输出
4