433. 最小基因变化

https://leetcode-cn.com/problems/minimum-genetic-mutation/

解法一：bfs

基本类似127题

import queue
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        res = []
        dict = set(bank)
        dict.add(start)
        nodeNeighbors = {}
        distances = {}
        distances[start] = 0
        
        self.bfs(start, end, dict, nodeNeighbors, distances)
        
        if end in distances:
            return distances[end]
        else:
            return -1
    
    def bfs(self, start, end, dict, nodeNeighbors, distances):
        for d in dict:
            nodeNeighbors[d] = []
        q = queue.Queue()
        q.put(start)
        
        while not q.empty():
            count = q.qsize()
            foundEnd = False
            
            for i in range(count):
                cur = q.get()
                neighbors = self.findNeighbors(cur, dict)
                for neighbor in neighbors:
                    if neighbor not in distances:
                        distances[neighbor] = distances[cur] + 1
                        if neighbor == end:
                            foundEnd = True
                        else:
                            q.put(neighbor)
            if foundEnd:
                break
    
    def findNeighbors(self, nodeString, dict):
        res = []
        chs = list(nodeString)
        for i in range(len(chs)):
            for ch in 'ACGT':
                if chs[i] == ch:
                    continue
                tmp = chs[i]
                chs[i] = ch
                newString = "".join(chs)
                if newString in dict:
                    res.append(newString)
                chs[i] = tmp
        return res