利用双向广度优先搜索算法解决。具体步骤如下:
- 定义两个队列 startQueue 和 endQueue,并分别将起点单词和终点单词添加到队列中。
- 定义两个集合 startVisited 和 endVisited,分别表示从起点和终点开始,已经访问过的单词。
同时也定义一个集合 midWords,存储中间必须出现的单词。
- 定义一个变量 length,存储单词阶梯的长度,初始化为 1。
- 进入循环,首先判断 startQueue 和 endQueue 是否为空,若其中有一个为空,则搜索结束,返回 0。
- 遍历 startQueue 中的所有单词,对于每个单词,枚举替换其中的每个字符,若替换后得到的单词存在于 endQueue 或 midWords 集合中,则搜索结束,返回 length+1。
若单词不存在于 startVisited 集合中,则将其添加到 startVisited 中,并将与该单词仅相差一个字符的单词加入 startQueue 中,表示下一步的可能路径。
- 同样的方式,在 endQueue 中进行处理。
- 如果 startQueue 中的单词数量比 endQueue 中多,则交换 startQueue 和 endQueue,增加搜索效率。
- length+1,继续搜索。
代码示例(Python):
def ladder_length(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
startQueue = [beginWord]
endQueue = [endWord]
startVisited = set([beginWord])
endVisited = set([endWord])
midWords = set(wordList) - set([beginWord, endWord])