题目分析

这道题目是一个路径搜索问题，每次只能改变一个字母，因此每一个单词都有邻接关系，求出从起始单词到终点单词的路径中最短的所有路径，这题难点不在于路径搜索，而是如何最高效的确定路径，因为要判断两个单词是否有邻接关系，遍历所有字符，而且逐个字符判断，**时间复杂度为$O(c * n^2)$**，有没有更好更快的方法呢？

邻接关系的确定

如果两两挑选，并且逐个字符判断，则**时间复杂度为$O(c * n^2)$，如果建立一个哈希表，里面存储缺省一个字符的所有匹配单词，则可以在时间复杂度为$O(c * n)$**的情况下确定邻接关系。
route

DFS

采用DFS来求解，沿着起始单词进行路径搜索，如果搜索到终点则记录长度，并且将路径保存，如果当前长度大于最优长度或者出现环，则剪枝，不继续搜索。最后从所有符合的路径中挑选出长度为最优长度的即可，因为初始最优长度设为无穷大，如果存在大量的环，DFS会耗费非常多的时间，因此不是最优的解法。

from collections import deque, defaultdict


class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        best_route = []
        best_n = float('inf')
        lens = len(beginWord)
        relation = defaultdict(list)
        list(map(lambda word: [relation[word[:i] + '*' + word[i + 1:]].append(word) for i in range(lens)], wordList))

        def dfs(current, n):
            nonlocal best_n
            if n > best_n or current[-1] in current[:-1]:
                return
            if current[-1] == endWord:
                best_route.append(current)
                best_n = len(current)
                return
            for i in range(lens):
                for next_word in relation[current[-1][:i] + '*' + current[-1][i + 1:]]:
                    dfs(current + [next_word], n + 1)

        dfs([beginWord], 1)
        return [x for x in best_route if len(x) == best_n]

BFS

想到最短路径就要想到广度优先搜索，因为广度优先搜索是从起点开始一层一层向外搜索，因此最先搜索到终点的路径一定是最短路径，为什么这道题目BFS比DFS快呢，因为BFS经过的路径不需要再次经过，所以建立一个passed集合，经过的点都记录在里面，下次直接跳过即可，注意这道题目要求所有的最短路径，只能每一层寻找完之后再加入passed集合，如果A-B-C是可以的，这时就将C加入passed集合，那么A-D-C就会被跳过，因此要将当前层都遍历后再修改passed集合。

class Solution(object):
    def findLadders(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: List[List[str]]
        """
        lens = len(beginWord)
        relation = defaultdict(list)
        list(map(lambda word: [relation[word[:i] + '*' + word[i + 1:]].append(word) for i in range(lens)], wordList))
        current_passed = set()
        passed = set().union([beginWord])
        current_queue = deque([[beginWord]])
        next_queue = deque()
        flag = False
        while True:
            while current_queue:
                current = current_queue.popleft()
                for i in range(lens):
                    for word in relation[current[-1][:i] + '*' + current[-1][i + 1:]]:
                        if word not in passed:
                            if word == endWord:
                                flag = True
                            current_passed.add(word)
                            next_queue.append(current + [word])
            if not next_queue:
                return []
            if flag:
                return [x for x in next_queue if x[-1] == endWord]
            else:
                passed.update(current_passed)
                current_queue = next_queue
                next_queue = deque()

刷题总结

路径搜索问题太经典了，多次强调BFS和DFS一定要牢记，两者绝大部分情况是可以相互转换的，但是可能存在着效率不同的问题，小伙伴们多多刷题，多多总结。