433. 最小基因变化（Minimum Genetic Mutation）题解

题目描述基因序列可以表示为一条由8 个字符组成的字符串其中每个字符都是A、C、G和T之一。假设我们需要调查从基因序列start变为end所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。另有一个基因库bank记录了所有有效的基因变化只有基因库中的基因才是有效的基因序列。变化后的基因必须位于基因库中。给你两个基因序列start和end以及一个基因库bank请你找出并返回能够使start变化为end所需的最少变化次数。如果无法完成基因变化返回-1。示例示例 1输入start AACCGGTT, end AACCGGTA, bank [AACCGGTA] 输出1示例 2输入start AACCGGTT, end AAACGGTA, bank [AACCGGTA,AACCGCTA,AAACGGTA] 输出2示例 3输入start AAAAACCC, end AACCCCCC, bank [AAAACCCC,AAACCCCC,AACCCCCC] 输出3提示start.length 8end.length 80 bank.length 10bank[i].length 8start、end和bank[i]仅由字符[A, C, G, T]组成题目分析每次基因变化只能改变一个字符变化后的基因必须存在于 bank 中我们要找到从start到end的最少变化次数这明显是一个最短路径问题每个基因序列可以看作一个节点节点之间的边表示它们之间只差 1 个字符。因此可以使用BFS广度优先搜索来求解最短路径。解题思路BFS 队列队列中存放当前的基因序列及其变化步数visited 数组标记 bank 中的基因是否已经访问过避免重复访问邻居判断两个基因序列如果只差 1 个字符则它们是相邻的可以互相转换BFS 搜索每次从队列取出一个序列尝试访问所有相邻序列一旦遇到end直接返回步数队列为空仍未找到则返回-1辅助函数判断两个基因序列是否相差 1 个字符int diff(char* a, char* b) { int cnt 0; for (int i 0; i 8; i) { if (a[i] ! b[i]) cnt; if (cnt 1) return 0; } return cnt 1; }C 语言 BFS 实现#include stdlib.h #include string.h int diff(char* a, char* b) { int cnt 0; for (int i 0; i 8; i) { if (a[i] ! b[i]) cnt; if (cnt 1) return 0; } return cnt 1; } int minMutation(char* startGene, char* endGene, char** bank, int bankSize) { int visited[10] {0}; // bank 最大长度为10 // BFS 队列 char* queue[100]; int step[100]; int front 0, rear 0; queue[rear] startGene; step[rear] 0; while (front rear) { char* cur queue[front]; int curStep step[front]; if (strcmp(cur, endGene) 0) return curStep; for (int i 0; i bankSize; i) { if (!visited[i] diff(cur, bank[i])) { visited[i] 1; queue[rear] bank[i]; step[rear] curStep 1; } } } return -1; }复杂度分析时间复杂度O(n² * 8)n bankSize队列最多访问 n 个节点每个节点需要比较 n 个邻居每个比较 8 次空间复杂度O(n)队列和 visited 数组由于题目中bankSize ≤ 10算法效率完全够用。总结本题是典型的最短路径 BFS问题核心是判断两个基因序列是否只差 1 个字符BFS 队列 visited 数组即可实现面试扩展可以枚举 8 个位置 A,C,G,T优化邻居判断对大规模基因序列更适用