难度: Medium
给定字典中的两个词，长度相等。写一个方法，把一个词转换成另一个词， 但是一次只能改变一个字符。每一步得到的新词都必须能在字典中找到。
编写一个程序，返回一个可能的转换序列。如有多个可能的转换序列，你可以返回任何一个。
示例 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" 不在字典中，所以不存在符合要求的转换序列。
运行时间: 64 ms
内存: 16.8 MB
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:
if beginWord == endWord: return 0
n = len(beginWord)
wordSet = set(wordList)
if endWord not in wordSet: return []
wordSet.remove(endWord)
start = defaultdict(list)
end = defaultdict(list)
start[beginWord].append(beginWord)
end[endWord].append(endWord)
while start:
if len(start) > len(end):
start, end = end, start
tmp = defaultdict(list)
for w in start:
for i in range(n):
for c in "abcdefghijklmnopqrstuvwxyz":
cur = w[:i] + c + w[i+1:]
if cur in end:
if start[w][0] == beginWord:
return start[w] + end[cur][::-1]
else:
return end[cur] + start[w][::-1]
if cur in wordSet:
tmp[cur] = start[w] + [cur]
wordSet.remove(cur)
start = tmp
return []
此题解采用了双向广度优先搜索（BFS）来找到从起始单词到结束单词的最短转换序列。使用两个字典start和end分别存储从起始单词和结束单词出发的可能路径。双向搜索的优势在于它可以从两个方向同时进行，当两边搜索相遇时，路径最短。每一轮迭代中，选择更小的字典进行扩展，以减少处理的单词数量。通过迭代当前字典中的所有单词，并对每个单词尝试改变每一个位置的字符，生成新词并检查是否存在于另一端的字典中或字典集wordSet中。如果生成的单词存在于对面的字典中，说明找到了一条路径。如果存在于wordSet中，则将其加入到临时字典tmp中，并从wordSet中删除，以防止重复访问。
时间复杂度: O(25nm)
空间复杂度: O(mn)
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[str]:
if beginWord == endWord: return 0
n = len(beginWord)
wordSet = set(wordList)
if endWord not in wordSet: return []
wordSet.remove(endWord)
start = defaultdict(list)
end = defaultdict(list)
start[beginWord].append(beginWord)
end[endWord].append(endWord)
while start:
if len(start) > len(end):
start, end = end, start # 优化搜索，始终扩展较小的字典
tmp = defaultdict(list)
for w in start:
for i in range(n):
for c in \"abcdefghijklmnopqrstuvwxyz\":
cur = w[:i] + c + w[i+1:]
if cur in end:
if start[w][0] == beginWord:
return start[w] + end[cur][::-1] # 如果起点开始的路径，则正序连接
else:
return end[cur] + start[w][::-1] # 如果终点开始的路径，则反序连接
if cur in wordSet:
tmp[cur] = start[w] + [cur] # 扩展新词，并记录路径
wordSet.remove(cur) # 移除已访问单词，避免重复访问
start = tmp
return [] # 如果无法连接，则返回空列表
在双向BFS中，选择更小的字典进行扩展可以显著减少遍历的单词数量和扩展的层级，从而减少计算量。这是因为扩展字典的大小直接影响到每一层迭代中需要探索的节点数。如果总是扩展较小的字典，可以更快地接近对方的搜索范围，从而更快找到中间相遇点，实现最短路径。这种优化显著提高了搜索效率，尤其是在大词汇集中。
尝试改变每个单词的每一个字符到其他任意字母（总共25个可能的改变），而不是直接尝试wordList中的单词，主要是因为这种方法可以更系统和全面地探索所有可能的单词变化。这样不仅可以检测到是否可以直接转变到wordList中的某个单词，同时也能发现那些可能未直接出现在wordList但作为中间步骤存在的单词。此外，这种方法在实现上更简单直接，不需要考虑wordList的特定排序或结构，提高了算法的通用性和效率。
将变化后的新词从wordSet中删除的主要优势是防止重复访问和处理，这样可以避免无效的循环和冗余计算，提高搜索效率。此外，它还有助于确保每个单词的访问路径是最短的，因为一旦一个单词被访问，其它任何通过更长路径到达该单词的尝试都会被忽略。可能的副作用包括，一旦删除了单词，如果算法需要回溯到某些特定的路径或状态，这种删除操作可能限制了回溯的可能性，因此设计算法时需要确保逻辑的正确性和充分性。