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