﻿ LeetCode Word Ladder II - 鸿网互联

原题

• 所有给出的字符串的长度都相等
• 所有的字符都为小写字母

``````  [
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]``````

解题思路

2. 现在是要求所有最少转换次数的转换方法，所以要将所有的转换可能都找出来。如图中bit和him转换为bim的转换关系我们都要找出来。
3. 我们还需要记录转换的路径，我们将从上一层到下一层的转换关系记录下来，等到确定能够转换成功了，再通过深度优先遍历的方法将转换路径组装起来。

AC源码

``````class Solution(object):
"""
:type beginWord: str
:type endWord: str
:type wordlist: Set[str]
:rtype: List[List[int]]
"""

def bfs(front_level, end_level, is_forward, word_set, path_dic):
if len(front_level) == 0:
return False
if len(front_level) > len(end_level):
return bfs(end_level, front_level, not is_forward, word_set, path_dic)
for word in (front_level | end_level):
next_level = set()
done = False
while front_level:
word = front_level.pop()
for c in 'abcdefghijklmnopqrstuvwxyz':
for i in range(len(word)):
new_word = word[:i] + c + word[i + 1:]
if new_word in end_level:
done = True
else:
if new_word in word_set:
return done or bfs(next_level, end_level, is_forward, word_set, path_dic)

if is_forward:
path_dic[word] = path_dic.get(word, []) + [new_word]
else:
path_dic[new_word] = path_dic.get(new_word, []) + [word]

def construct_path(word, end_word, path_dic, path, paths):
if word == end_word:
paths.append(path)
return
if word in path_dic:
for item in path_dic[word]:
construct_path(item, end_word, path_dic, path + [item], paths)

front_level, end_level = {beginWord}, {endWord}
path_dic = {}
bfs(front_level, end_level, True, wordlist, path_dic)
path, paths = [beginWord], []
construct_path(beginWord, endWord, path_dic, path, paths)
return paths

if __name__ == "__main__":
assert Solution().findLadders("hit", "cog", {"hot", "dot", "dog", "lot", "log"}) == [
["hit", "hot", "dot", "dog", "cog"],
["hit", "hot", "lot", "log", "cog"]
]``````

<