字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk: 每一对相邻的单词只差一个字母。 对于 1 <= i <= k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。 sk == endWord 给你两个单词 beginWord 和 endWord 和一个字典 wordList ,返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列,返回 0
时间: 2024-03-10 14:48:17 浏览: 128
这是一个经典的图论问题,可以使用广度优先搜索算法(BFS)来解决。
首先,我们将所有的单词加入到一个集合中,便于后续的查询。然后,我们定义一个队列,将 beginWord 加入队列中,并将其标记为已访问。接着,我们开始进行 BFS。
在 BFS 的过程中,我们每次从队列中取出一个单词,然后枚举其所有可能的下一个单词。对于每个下一个单词,如果它在集合中存在且没有被访问过,我们就将其加入队列,并将其标记为已访问。如果当前单词等于 endWord,说明我们已经找到了一条最短路径,直接返回当前路径长度即可。
如果在 BFS 结束后仍然没有找到一条从 beginWord 到 endWord 的路径,说明不存在这样的转换序列,返回 0。
下面是 Python 代码实现:
```python
from collections import deque
def ladderLength(beginWord: str, endWord: str, wordList: List[str]) -> int:
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([(beginWord, 1)])
visited = set([beginWord])
while queue:
word, length = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for j in range(26):
nextWord = word[:i] + chr(ord('a') + j) + word[i+1:]
if nextWord in wordSet and nextWord not in visited:
queue.append((nextWord, length + 1))
visited.add(nextWord)
return 0
```
阅读全文