126. 单词接龙 II

https://leetcode-cn.com/problems/word-ladder-ii/

解法一：dfs+bfs

import queue
class Solution:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        self.res = []  #全局变量，记录输出
        nodeNeighbors = {}  #map，k为结点名，v为结点的所有邻居名
        dict = set(wordList)  #存储所有结点名
        distances = {}  #map，k为结点名，v为起点到该节点的距离
        solution = []  #dfs辅助变量，暂存路径，用于回溯
        
        dict.add(beginWord)
        #把每个单词看做一个结点，先用一遍bfs遍历建立图结构，得到所有结点的相邻结点信息nodeNeighbors，并得到从起点到终点的最短距离
        self.bfs(beginWord, endWord, dict, nodeNeighbors, distances)
        #再用一遍dfs回溯输出所有从起点到终点的最短路径
        self.dfs(beginWord, endWord, dict, nodeNeighbors, distances, solution)

        return self.res
    
    #广度优先搜索，一层一层向外访问（类似二叉树层序）
    def bfs(self, start, end, dict, nodeNeighbors, distances):
        for d in dict:
            nodeNeighbors[d] = []
       #初始化         
        q = queue.Queue()
        q.put(start)
        distances[start] = 0
        
        while not q.empty():
            count = q.qsize()  #该层规模
            foundEnd = False  #标志位，该层是否能到达终点
            
            for i in range(count):  #遍历该层所有结点
                cur = q.get()
                neighbors = self.getNeighbors(cur, dict)
                print(i, cur , neighbors)
                print(nodeNeighbors[cur])
                for neighbor in neighbors:
                    nodeNeighbors[cur].append(neighbor)
                    if neighbor not in distances:  #避免重复访问
                        distances[neighbor] = distances[cur] + 1
                        if neighbor == end:  #到达终点
                            foundEnd = True
                        else:
                            q.put(neighbor)
            if foundEnd:  #若该层能到达终点，则不再访问下一层（求最短距离）
                break
   
   #求某个结点的所有相邻结点     
    def getNeighbors(self, nodeString, dict):
        res = []
        chs = list(nodeString)
        #对每个字符，分别将其替换成另外的25个字符
        for i in range(len(chs)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                if ch == chs[i]:  #跳过原字符，换成其他字符
                    continue
                tmp = chs[i]  #暂存原字符
                chs[i] = ch  #替换
                newString = "".join(chs)
                if newString in dict:  #找到在wordList中的字符串
                    res.append(newString)
                chs[i] = tmp  #还原
        return res                      
                    
   #深度优先遍历，回溯输出所有最短路径，solution暂存当前路径         
    def dfs(self, cur, end, dict, nodeNeighbors, distances, solution):
        solution.append(cur)  #尝试写入当前节点
        if cur == end:  #若能到达终点，将当前路径复制加入全局res
            self.res.append(list(solution))
        #对当前节点的所有邻居
        for next in nodeNeighbors[cur]:
         	#关键，保证向下一级访问（不回头）
            if distances[next] == distances[cur] + 1:
                self.dfs(next, end, dict, nodeNeighbors, distances, solution)
        solution.pop()  #弹出当前节点