127. 单词接龙

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

解法一：bfs

思路和126差不多，区别在于只用bfs，每次访问一层，用一个map来存储访问过的结点以及与起点的距离，避免重复访问。最后输出map中的终点项即可

import queue
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        nodeNeighbors = {}  #所有邻居信息
        dict = set(wordList)
        distances = {}  #所有距离信息
        
        dict.add(beginWord)
        self.bfs(beginWord, endWord, dict, nodeNeighbors, distances)

        if endWord in distances:
            return distances[endWord] + 1
        else:  #若不存在，说明无法到达
            return 0
        
    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)
                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)
        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:
                    res.append(newString)
                chs[i] = tmp  #还原
        return res