Python | Leetcode Python题解之第433题最小基因变化

题目：

题解：

class Solution:def minMutation(self, start: str, end: str, bank: List[str]) -> int:if start == end:return 0def diffOne(s: str, t: str) -> bool:return sum(x != y for x, y in zip(s, t)) == 1m = len(bank)adj = [[] for _ in range(m)]endIndex = -1for i, s in enumerate(bank):if s == end:endIndex = ifor j in range(i + 1, m):if diffOne(s, bank[j]):adj[i].append(j)adj[j].append(i)if endIndex == -1:return -1q = [i for i, s in enumerate(bank) if diffOne(start, s)]vis = set(q)step = 1while q:tmp = qq = []for cur in tmp:if cur == endIndex:return stepfor nxt in adj[cur]:if nxt not in vis:vis.add(nxt)q.append(nxt)step += 1return -1