九章算法 | 拼多多面试题：单词接龙 II

描述

给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。

变换规则如下：

1. 每次只能改变一个字母。
2. 变换过程中的中间单词必须在字典中出现。

• 所有单词具有相同的长度。
• 所有单词都只包含小写字母。
• 题目确保存在合法的路径。

在线评测地址：领扣-程序员的代码评测平台

样例1

输入：start = "a"，end = "c"，dict =["a","b","c"] 
输出：[["a","c"]] 
解释： 
"a"->"c" 

样例2

输入：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 到 start 做一次 BFS，并且把距离 end 的距离都保存在 distance 中。 然后在从 start 到 end 做一次 DFS，每走一步必须确保离 end 的 distance 越来越近。

与另外一个代码中提前建立 index 不同，这里是在寻找下一个变换单词的时候，再去获得对应的单词列表。一个单词最多有 L 个字符，每个字符有 25 种不同的变化（26个字母除掉这个位置上的字母），然后 check 一下在不在 dict 里就知道是不是 next word 了。

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 
    """ 
    def findLadders(self, start, end, dict): 
        dict.add(start) 
        dict.add(end) 
        distance = {} 
 
        self.bfs(end, distance, dict) 
 
        results = [] 
        self.dfs(start, end, distance, dict, [start], results) 
 
        return results 
 
    def bfs(self, start, distance, dict): 
        distance[start] = 0 
        queue = deque([start]) 
        while queue: 
            word = queue.popleft() 
            for next_word in self.get_next_words(word, dict): 
                if next_word not in distance: 
                    distance[next_word] = distance[word] + 1 
                    queue.append(next_word) 
 
    def get_next_words(self, word, dict): 
        words = [] 
        for i in range(len(word)): 
            for c in 'abcdefghijklmnopqrstuvwxyz': 
                next_word = word[:i] + c + word[i + 1:] 
                if next_word != word and next_word in dict: 
                    words.append(next_word) 
        return words 
 
    def dfs(self, curt, target, distance, dict, path, results): 
        if curt == target: 
            results.append(list(path)) 
            return 
 
        for word in self.get_next_words(curt, dict): 
            if distance[word] != distance[curt] - 1: 
                continue 
            path.append(word) 
            self.dfs(word, target, distance, dict, path, results) 
            path.pop() 

更多题解参考：九章算法