公司招了个30岁新人，结果入职第一天就辞职了，理由是停车场没超20w的车。。。

不得不说，刷题这件事，真的像谈恋爱：一开始兴致勃勃，做了一题就想发朋友圈，后来一看到 hard 难度就像前任朋友圈点赞新男友——心态直接炸裂。

这不，今天遇到一道生猛的算法题——最小基因变化。看名字挺像《生化危机》的剧本，其实本质就是个典型的 图的最短路径问题。题目大概意思是：

给定一个起始基因串 start，一个目标基因串 end，还有一个合法基因库 bank。每次可以变换一个字符（A、C、G、T 四选一），但前提是变化后的字符串得在 bank 里。问你最少几步能从 start 变成 end。

看到这种“一步一步变，必须走合法节点”的题，第一反应就是：👀BFS 它不香吗？

来，直接上代码先压压惊👇：

from collections import deque

defminMutation(start: str, end: str, bank: list[str]) -> int:
if end notin bank:
return-1# 如果目标都不在bank里，那肯定去不到

    gene_choices = ['A', 'C', 'G', 'T']
    bank_set = set(bank)  # 提高查找效率
    visited = set()
    queue = deque([(start, 0)])  # 存储当前基因串和变换次数

while queue:
        current, steps = queue.popleft()
if current == end:
return steps

for i in range(len(current)):
for gene in gene_choices:
if gene == current[i]:
continue
                mutated = current[:i] + gene + current[i+1:]
if mutated in bank_set and mutated notin visited:
                    visited.add(mutated)
                    queue.append((mutated, steps + 1))

return-1# 走不到目标

我觉得这题看似算法，实则人生。

你以为是贪心，其实不然。每一步必须严丝合缝地变，变错一步就掉坑。这不就像职场里的转岗吗？你得提前做好准备，有对应的能力支持，才能一步步“合法跳转”。否则转过去一脸懵，领导说你是“非法基因”，直接告辞。

回到技术点，这题的核心是 BFS（广度优先搜索），原因也很简单：我们要求“最少几步”。DFS 也不是不能做，就是容易走弯路，可能从北京出发转一圈澳大利亚再回来，结果你邻居从天津顺风就到了……你说气不气？😂

这里还有个常见的坑：bank 很大，查找的时候如果用 list 就容易超时。所以我会把它转换成 set。别小看这个操作，有时候面试官就喜欢让你说出这种“优化的小技巧”，答不上来就会被“合法剔除”。

再说个我觉得很有意思的点：虽然题目说的只是四种字符的变化，其实也可以把每个基因串当成图中的一个节点，只要两个基因之间差一个字符，那它们之间就连一条边。于是整个问题就变成了找从 start 到 end 的最短路径。

很多人刷题容易掉进另一个坑：明明题是图，非要当字符串去搞，把自己搞得像八爪鱼打电话——绕来绕去结果全缠一起了。

当然了，也有人非要用 A，说能剪枝。但我觉得这题本身图不大，BFS已经非常够用了，用 A 有点像走楼梯非得穿火箭靴——太激动了兄弟。

总结一下哈（不是官方总结，就是程序员版碎碎念）：遇到“逐步变化”的题，要想的是路径而不是变化本身。每一个中间态都要合法，就像你写代码每一步都得过 linter，不然上线直接爆炸；而 BFS 是最靠谱的“代码走查工具”，能一步步带你走到目标，还不容易走岔路。