题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。
编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
示例 1:
- 输入:
- beginWord = "hit",
- endWord = "cog",
- wordList = ["hot","dot","dog","lot","log","cog"]
- 输出:
- ["hit","hot","dot","lot","log","cog"]
示例 2:
- 输入:
- beginWord = "hit"
- endWord = "cog"
- wordList = ["hot","dot","dog","lot","log"]
- 输出: []
- 解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
题目思考
- 如何找到可以直接转换的有效单词?
- 如何得到转换序列?
解决方案
思路
- 分析题目, 我们需要判断各个单词是否在字典中, 所以我们可以先将给定的单词字典(列表)转成集合, 优化查找的时间复杂度
- 接下来就是找可以转换的单词, 这里有两种思路:
- 思路 1: 遍历整个字典(假设有 N 个单词), 找所有与当前单词只相差一个字符的单词 (假设单词平均长度为 C), 时间复杂度是 O(NC)
- 思路 2: 从当前单词出发, 遍历其每个字符下标, 并将其替换成剩余 25 个字母, 从而构造出新的单词, 然后如果该单词在字典中则说明它有效, 时间复杂度是 O(25*C)
- 通过比较, 显然思路 2 的方案更优, 它的效率跟字典的单词个数无关
- 找到了可以转换的单词, 接下来就是确定符合要求的转换序列
- 这里我们可以采用 BFS 的思想, 结合一个 visit 集合来避免重复遍历
- 注意由于我们需要构造出整个转换序列, 所以这里需要将 visit 集合升级成一个前向映射字典
- 该字典的 key 是当前单词, value 是前一个单词, 这样它就兼具了避免重复遍历, 以及构造出转换序列的功能
- 具体做法就是找到终点单词后, 根据前向映射字典依次找到其前面的单词, 直到达到起点单词为止, 对应的序列的逆序即为最终要求的转换序列
- 下面代码有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(NC): 假设字典的单词数目是 N, 每个单词的平均长度是 C, 那么每个单词最多遍历一次, 这部分时间是 O(N), 而找邻居单词需要遍历整个单词并替换成其他 25 个字母, 这部分时间是 O(25*C), 所以总时间复杂度是 O(NC) - 空间复杂度
O(NC): 维护了一个最多有 N 个单词的映射字典
代码
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:
# BFS+前向映射字典
# 先将给定的单词字典转成集合, 优化查找的时间复杂度
ws = set(wordList)
if endWord not in ws:
# 终点单词不在字典中, 无法转换
return []
q = [beginWord]
# 记录转换序列中当前单词到前一个单词的映射关系
# 例如a->b->c, 则字典存储{c:b}和{b:a}
preDict = {}
def getNextWord(w):
# 找到每个单词的所有只更改一个字符的邻居单词
# 例如abc更改第一个字符的邻居单词就是[bbc,cbc,...,zbc]
for i in range(len(w)):
# 尝试更改第i个下标的字符
for o in range(26):
c = chr(o + ord("a"))
if c != w[i]:
# 需要保证该字符不等于原始字符
nex = w[:i] + c + w[i + 1 :]
yield nex
for w in q:
for nex in getNextWord(w):
if nex in ws and nex not in preDict:
# 如果相邻字符在字典中, 且不在前向映射字典中(表示该单词尚未遍历过), 则可以将其加入转换序列中
# 更新前向映射字典
preDict[nex] = w
if nex == endWord:
# 该单词恰好等于终点单词, 说明找到了一个有效转换序列
# 然后利用前向映射字典, 重建整个转换序列
res = []
while True:
res.append(nex)
if nex == beginWord:
# 达到起点单词, 跳出循环
break
# 找转换序列的前一个单词
nex = preDict[nex]
# 注意加入单词的顺序是从终点单词开始, 所以最终结果需要逆序
return res[::-1]
q.append(nex)
return []
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号