LintCode 121. 单词接龙 II
题目描述
给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。
变换规则如下：
1. 每次只能改变一个字母。
2. 变换过程中的中间单词必须在字典中出现。
注意事项
所有单词具有相同的长度。
所有单词都只包含小写字母。
题目确保存在合法的路径。
测试样例
输入：start = "a"，end = "c"，dict =["a","b","c"]
输出：[["a","c"]]
解释：
"a"->"c"
输入：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"
第一个序列的字典序小于第二个。
解题思路
首先从end开始反向构建层级关系，提供可行的所有路径，既然是层级关系，那么就很自然会使用BFS。
在BFS对每层进行搜索时，需要记录下搜索的下一层每个单词距end的距离，可用一个dict来记录，此处记为distance，key就是搜索到的下一层单词，value是对应距end的距离，设置为上一层单词距离加1。另外，搜索到的词还需要满足之前没有被distance记录，即不在distance的key中，避免构建循环路径。
这里讲下搜索单词的方法：
对单词的每个字母位置依次进行替换，每个位置有25种可能（26个字母除去当前字母），然后判断替换后的词是否在字典中。如果是，则作为搜索到的下一个单词。
BFS构建完层级关系后，就从start开始进行DFS，搜寻符合要求的每条目标路径。DFS搜索单词的方法如同上述，但是需要外加一个条件——搜索到的下个词距离end必须比当前这个词更近1。最后搜索至当前的词为end后将整条路径加入结果集并终止搜索。
另外，还有一种搜索单词的方法：
对字典中的每个单词，将其每个位置的字母用'%'代替，构建一个patten，作为key，value设置为原来的这个单词，将这样的一个个key-value对存到一个dict中，之后在BFS和DFS中就通过这个dict来查询搜索的词，而不再使用原先的字典。
代码
1.
from collections import deque
class Solution:
"""
@param: start: a string
@param: end: a string
@param: dict: a set of string
@return: a list of lists of string
"""
L = sys.maxsize
def findLadders(self, start, end, dict):
if len(start) == 1 and len(end) == 1:
return [[start, end]]
# 记录路径中各个词到end的距离
dis = {}
# 将start，end加入字典，注意不要写成.union(start, end)！
dict = dict.union([start, end])
# 从end开始反向进行宽度优先搜索，建立层级关系
self._BFS(end, dis, dict)
result = []
# 从start开始进行深搜，寻找每条目标路径
self._DFS(start, end, dis, dict, [start], result)
return result
def _DFS(self, cur, target, dis, dic, path, result):
if cur == target:
result.append(path)
return
for next_word in self._get_next_words(cur, dic):
# 必须满足下一个词的距离end比当前词距离end更近1
if dis[cur] - dis[next_word] == 1:
self._DFS(next_word, target, dis, dic, path + [next_word], result)
def _BFS(self, begin, dis, dic):
dis[begin] = 0
queue = deque([begin])
while queue:
cur = queue.popleft()
for next_word in self._get_next_words(cur, dic):
# 注意下一个词需要未被dis记录
# 避免构建循环路径
if next_word not in dis:
dis[next_word] = dis[cur] + 1
queue.append(next_word)
def _get_next_words(self, word, dic):
"""寻找下一个可能的词，其必须在字典中"""
next_words = []
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
if c == word[i]:
continue
next_word = word[:i] + c + word[i + 1:]
if next_word in dic:
next_words.append(next_word)
return next_words
2.
from collections import deque
class Solution:
"""
@param: start: a string
@param: end: a string
@param: dict: a set of string
@return: a list of lists of string
"""
L = sys.maxsize
def findLadders(self, start, end, dict):
if len(start) == 1 and len(end) == 1:
return [[start, end]]
# 将start，end加入字典，注意不要写成.union(start, end)！
dict = dict.union([start, end])
# 对字典中每个词的替换模式都构建对应的映射关系
# 将每个词的各个位置替换为'%'作为key，value是该词本身
maps = self._build_maps(dict)
# 从end开始反向进行宽度优先搜索，建立层级关系
dis = self._BFS(end, maps)
result = []
# 从start开始进行深搜，寻找每条目标路径
self._DFS(start, end, dis, maps, [start], result)
return result
def _build_maps(self, dic):
maps = {}
for word in dic:
for i in range(len(word)):
pattern = word[:i] + '%' + word[i + 1:]
if pattern in maps:
maps[pattern].add(word)
else:
maps[pattern] = set([word])
return maps
def _DFS(self, cur, target, dis, maps, path, result):
if cur == target:
result.append(path)
return
for next_word in self._get_next_words(cur, maps):
# 必须满足下一个词的距离end比当前词距离end更近1
if dis[cur] - dis[next_word] == 1:
self._DFS(next_word, target, dis, maps, path + [next_word], result)
def _BFS(self, begin, maps):
# 记录路径中各词到目标的距离
dis = {begin: 0}
queue = deque([begin])
while queue:
cur = queue.popleft()
for next_word in self._get_next_words(cur, maps):
# 注意下一个词需要未被dis记录
# 避免构建循环路径
if next_word not in dis:
dis[next_word] = dis[cur] + 1
queue.append(next_word)
return dis
def _get_next_words(self, word, maps):
"""寻找下一个可能的词，其必须在字典中"""
next_words = []
for i in range(len(word)):
next_key = word[:i] + '%' + word[i + 1:]
for next_word in maps.get(next_key, []):
next_words.append(next_word)
return next_words
