0433. Minimum Genetic Mutation¶
题目信息¶
- 题号:
0433
- 难度:
Medium
- 主题:
八位基因、单字符突变、基因库、最少步数
- 原题:
- 重点:
每步恰好修改一个字符、修改后基因必须在
bank中、字符仅限A/C/G/T、不可达返回-1
题目重述¶
基因字符串长度固定为 8,只包含字符 A、C、G、T。一次突变必须恰好改变一个位置的字符。给定起始基因 startGene、目标基因 endGene 和合法基因库 bank,返回从起点变到终点所需的最少突变次数。
除起始基因外,每次突变后得到的基因都必须存在于 bank 中;起始基因本身不要求在库中。若无法到达目标,返回 -1。bank.length 位于 [0, 10],其中基因互不相同;若起点和终点相同,最少突变次数为 0。
自建示例¶
需要连续四次合法突变:
输入:startGene = "AAAAAAAA"
endGene = "AAAACCCC"
bank = ["AAAAAAAC", "AAAAAACC", "AAAAACCC", "AAAACCCC"]
输出:4
解释:可以按基因库给出的顺序每次把一个 A 改为 C,四个中间或最终基因都在 bank 中。
终点不在合法路径中:
输入:startGene = "AACCGGTT"
endGene = "AACCGGTA"
bank = []
输出:-1
解释:终点与起点只差一个字符,但突变后的基因不在 bank 中,因此该突变不合法。
基因字符串构成无权图,BFS 首次到达即最短¶
每个合法基因是一个图节点,相差恰好一个字符的两个基因之间有边;但只有目标字符串在 bank 中时,才允许把它作为突变后的节点。一次突变代价相同,所以从 startGene 广度优先搜索,首次到达 endGene 的层数就是最少次数。
对当前基因的每个位置尝试另外三种碱基,并用集合判断候选是否在库中、是否已经访问;起点和终点相同时在搜索前直接返回 0。
C++ 实现¶
class Solution {
public:
int minMutation(std::string startGene, std::string endGene,
std::vector<std::string>& bank) {
if (startGene == endGene) return 0;
std::unordered_set<std::string> available(
bank.begin(), bank.end());
if (available.count(endGene) == 0) return -1;
std::queue<std::pair<std::string, int>> queue;
queue.push({startGene, 0});
std::unordered_set<std::string> visited = {startGene};
const std::string genes = "ACGT";
while (!queue.empty()) {
auto [current, distance] = queue.front();
queue.pop();
for (int i = 0; i < 8; ++i) {
std::string next = current;
for (char gene : genes) {
if (gene == current[i]) continue;
next[i] = gene;
if (available.count(next) == 0
|| visited.count(next) != 0) {
continue;
}
if (next == endGene) return distance + 1;
visited.insert(next);
queue.push({next, distance + 1});
}
}
}
return -1;
}
};
代码分析¶
BFS 按突变次数分层,访问标记避免同一基因反复入队;每个状态只尝试 8 * 3 个有限变更。时间复杂度为 O(B * 8 * 3)``(``B 为基因库规模),额外空间为 O(B)。