LeetCode 433. 最小基因变化
字数 2903 2025-10-26 11:43:54

LeetCode 433. 最小基因变化

题目描述

一条基因序列由一个长度为8的字符串表示，其中每个字符都是 'A', 'C'', 'G', 'T' 之一。

假设我们需要研究从起始基因序列 startGene 到目标基因序列 endGene 之间的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
此外，还有一个基因库 bank，它记录了所有有效的基因变化序列。只有存在于基因库中的基因序列才是有效的。

请你找出并返回能够使 startGene 变化为 endGene 所需的最少变化次数。如果无法完成此变化，返回 -1。

注意：起始基因序列 startGene 默认是有效的，但是它并不一定会出现在基因库中。endGene 必须在基因库中。

示例 1：
输入：startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
输出：1
解释：只需一次变化，将末尾的 'T' 变为 'A'。

示例 2：
输入：startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2
解释：路径可以是 "AACCGGTT" -> "AACCGGTA" -> "AAACGGTA"。

解题过程

这个问题可以被看作是在一个图中寻找最短路径。我们可以将每个基因序列视为图中的一个节点。如果两个基因序列之间只有一个字符的差异，那么就在这两个节点之间连一条边。我们的目标就是找到从起始节点（startGene）到目标节点（endGene）的最短路径（即最少的边数，也就是最少的变化次数）。

广度优先搜索（BFS）是解决无权图最短路径问题的理想算法。

步骤 1：问题分析与建模

  1. 状态（节点）：每个可能的基因序列就是一个状态。
  2. 边：如果基因序列 A 可以通过改变一个字符（在 'A', 'C', 'G', 'T' 中变化）变成基因序列 B，并且这个序列 B 存在于基因库 bank 中（或者恰好是目标序列），那么我们就认为从 A 到 B 有一条边。
  3. 目标：使用 BFS 从 startGene 开始，一层一层地扩展，直到我们找到 endGene。BFS 的层数就是所需的最小变化次数。

步骤 2：数据结构准备

  1. 基因库集合（bankSet）： 为了快速判断一个基因变化是否有效（即新序列是否在基因库中），我们将列表 bank 转换为一个集合（Set）。在集合中检查元素是否存在的时间复杂度是 O(1)。
  2. 访问记录集合（visited）： 我们需要记录已经访问过的基因序列，以避免重复访问和陷入无限循环。通常使用一个集合来实现。
  3. 队列（queue）： BFS 的核心数据结构。队列中存储的是当前待处理的基因序列以及从起点到该序列所需的步数（变化次数）。在 Python 中，我们可以使用 collections.deque。

步骤 3：算法核心步骤（BFS）

  1. 初始化：

    • 如果 startGene 已经等于 endGene，那么不需要变化，直接返回 0。
    • 将 (startGene, 0) 放入队列。0 表示从起点到起点需要 0 步。
    • 将 startGene 加入 visited 集合，表示已经访问过。

  2. 循环处理队列，直到队列为空：
    a. 从队列的头部取出一个节点，包含当前基因序列 current_gene 和当前步数 steps。
    b. 遍历当前基因序列的每一个位置（索引从 0 到 7）。
    c. 对于每个位置，依次尝试将其字符替换为 'A', 'C', 'G', 'T'（但要排除它自身当前的字符，避免生成和原来一样的序列）。
    d. 对于每一个新生成的基因序列 next_gene：
    * 如果 next_gene 等于 endGene，那么我们已经找到了目标！返回 steps + 1。
    * 如果 next_gene 存在于 bankSet 中 并且 还没有被访问过：
    - 将其标记为已访问（加入 visited 集合）。
    - 将 (next_gene, steps + 1) 这个新状态加入队列的尾部。这表示我们通过一次变化，从 current_gene 到达了 next_gene，总步数增加了 1。

  3. 处理结果：

    • 如果 BFS 过程结束（队列为空）我们都没有遇到 endGene，说明从 startGene 无法变化到 endGene，返回 -1。

为什么 BFS 能找到最短路径？
BFS 是按“层”遍历的。首先访问所有距离起点为 1 步的节点，然后访问所有距离为 2 步的节点，以此类推。因此，当它第一次遇到目标节点时，所经过的步数必然是最小的。

步骤 4：关键点与优化

  • 提前终止：在生成新序列后，先判断是否等于目标，可以提前返回结果，节省时间。
  • 访问标记：必须在将节点加入队列的同时就进行标记，而不是在从队列中取出时才标记。这样可以防止同一个节点被多次加入队列，尤其是在图中存在环的情况下（虽然本题基因库有限，但重复访问也是无意义的）。

图解示例 2 的 BFS 过程

起点：AACCGGTT (步骤 0)
第一层变化（步骤 1）：生成所有与起点差一个字符且在基因库中的序列。

  • 将第一个字符 'A' 变为 'A'（跳过自身）、'C'、'G'、'T'... 检查 CACCGGTT, GACCGGTT, TACCGGTT 是否在 bank 中？不在。
  • 改变第二个字符 ... 最终发现，改变第七个字符 'T' 可以变成 AACCGGTA，这个序列在 bank 中。将其加入队列。此时队列：[(AACCGGTA, 1)]

处理第一层节点 AACCGGTA (步骤 1)：
从它开始生成新序列。

  • 改变第一个字符 ... 发现变成 AACCGGTA（跳过自身）、CACCGGTA... 不在 bank。
  • 改变第二个字符 ... 发现将 'A' 变成 'A'（跳过）... 变成 'C' -> ACCCGGTA 不在 bank。
  • ... 改变第三个字符 ... 将 'C' 变成 'A' -> AAACGGTA。这个序列在 bank 中，并且它就是我们的目标 endGene！

算法结束，返回当前步骤 (1) + 1 = 2。

总结
通过将问题建模为图，并使用 BFS 进行层序遍历，我们可以高效地找到从起始基因到目标基因的最短变化路径。算法的核心在于状态表示、邻居生成（通过单字符替换）和利用集合进行快速的有效性校验与访问控制。

LeetCode 433. 最小基因变化 题目描述 一条基因序列由一个长度为8的字符串表示，其中每个字符都是 'A' , 'C'', 'G' , 'T' 之一。 假设我们需要研究从起始基因序列 startGene 到目标基因序列 endGene 之间的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 例如， "AACCGGTT" --> "AACCGGTA" 就是一次基因变化。 此外，还有一个基因库 bank ，它记录了所有有效的基因变化序列。只有存在于基因库中的基因序列才是有效的。 请你找出并返回能够使 startGene 变化为 endGene 所需的最少变化次数。如果无法完成此变化，返回 -1 。 注意：起始基因序列 startGene 默认是有效的，但是它并不一定会出现在基因库中。 endGene 必须在基因库中。 示例 1： 输入：startGene = "AACCGGTT", endGene = "AACCGGTA", bank = [ "AACCGGTA" ] 输出：1 解释：只需一次变化，将末尾的 'T' 变为 'A'。 示例 2： 输入：startGene = "AACCGGTT", endGene = "AAACGGTA", bank = [ "AACCGGTA","AACCGCTA","AAACGGTA" ] 输出：2 解释：路径可以是 "AACCGGTT" -> "AACCGGTA" -> "AAACGGTA"。 解题过程 这个问题可以被看作是在一个图中寻找最短路径。我们可以将每个基因序列视为图中的一个节点。如果两个基因序列之间只有一个字符的差异，那么就在这两个节点之间连一条边。我们的目标就是找到从起始节点（ startGene ）到目标节点（ endGene ）的最短路径（即最少的边数，也就是最少的变化次数）。 广度优先搜索（BFS）是解决无权图最短路径问题的理想算法。 步骤 1：问题分析与建模 状态（节点） ：每个可能的基因序列就是一个状态。 边 ：如果基因序列 A 可以通过改变一个字符（在 'A', 'C', 'G', 'T' 中变化）变成基因序列 B，并且这个序列 B 存在于基因库 bank 中（或者恰好是目标序列），那么我们就认为从 A 到 B 有一条边。 目标 ：使用 BFS 从 startGene 开始，一层一层地扩展，直到我们找到 endGene 。BFS 的层数就是所需的最小变化次数。 步骤 2：数据结构准备 基因库集合（ bankSet ） ： 为了快速判断一个基因变化是否有效（即新序列是否在基因库中），我们将列表 bank 转换为一个集合（Set）。在集合中检查元素是否存在的时间复杂度是 O(1)。 访问记录集合（ visited ） ： 我们需要记录已经访问过的基因序列，以避免重复访问和陷入无限循环。通常使用一个集合来实现。 队列（ queue ） ： BFS 的核心数据结构。队列中存储的是当前待处理的基因序列以及从起点到该序列所需的步数（变化次数）。在 Python 中，我们可以使用 collections.deque 。 步骤 3：算法核心步骤（BFS） 初始化 ： 如果 startGene 已经等于 endGene ，那么不需要变化，直接返回 0 。 将 (startGene, 0) 放入队列。 0 表示从起点到起点需要 0 步。 将 startGene 加入 visited 集合，表示已经访问过。 循环处理队列，直到队列为空 ： a. 从队列的头部取出一个节点，包含当前基因序列 current_gene 和当前步数 steps 。 b. 遍历当前基因序列的每一个位置（索引从 0 到 7）。 c. 对于每个位置，依次尝试将其字符替换为 'A' , 'C' , 'G' , 'T' （但要排除它自身当前的字符，避免生成和原来一样的序列）。 d. 对于每一个新生成的基因序列 next_gene ： * 如果 next_gene 等于 endGene ，那么我们已经找到了目标！返回 steps + 1 。 * 如果 next_gene 存在于 bankSet 中 并且 还没有被访问过： - 将其标记为已访问（加入 visited 集合）。 - 将 (next_gene, steps + 1) 这个新状态加入队列的尾部。这表示我们通过一次变化，从 current_gene 到达了 next_gene ，总步数增加了 1。 处理结果 ： 如果 BFS 过程结束（队列为空）我们都没有遇到 endGene ，说明从 startGene 无法变化到 endGene ，返回 -1 。 为什么 BFS 能找到最短路径？ BFS 是按“层”遍历的。首先访问所有距离起点为 1 步的节点，然后访问所有距离为 2 步的节点，以此类推。因此，当它第一次遇到目标节点时，所经过的步数必然是最小的。 步骤 4：关键点与优化 提前终止 ：在生成新序列后，先判断是否等于目标，可以提前返回结果，节省时间。 访问标记 ：必须在将节点加入队列的同时就进行标记，而不是在从队列中取出时才标记。这样可以防止同一个节点被多次加入队列，尤其是在图中存在环的情况下（虽然本题基因库有限，但重复访问也是无意义的）。 图解示例 2 的 BFS 过程 起点： AACCGGTT (步骤 0) 第一层变化（步骤 1）：生成所有与起点差一个字符且在基因库中的序列。 将第一个字符 'A' 变为 'A'（跳过自身）、'C'、'G'、'T'... 检查 CACCGGTT , GACCGGTT , TACCGGTT 是否在 bank 中？不在。 改变第二个字符 ... 最终发现，改变第七个字符 'T' 可以变成 AACCGGTA ，这个序列在 bank 中。将其加入队列。此时队列： [(AACCGGTA, 1)] 处理第一层节点 AACCGGTA (步骤 1)： 从它开始生成新序列。 改变第一个字符 ... 发现变成 AACCGGTA （跳过自身）、 CACCGGTA ... 不在 bank。 改变第二个字符 ... 发现将 'A' 变成 'A'（跳过）... 变成 'C' -> ACCCGGTA 不在 bank。 ... 改变第三个字符 ... 将 'C' 变成 'A' -> AAACGGTA 。这个序列在 bank 中，并且它就是我们的目标 endGene ！ 算法结束，返回当前步骤 (1) + 1 = 2。 总结 通过将问题建模为图，并使用 BFS 进行层序遍历，我们可以高效地找到从起始基因到目标基因的最短变化路径。算法的核心在于状态表示、邻居生成（通过单字符替换）和利用集合进行快速的有效性校验与访问控制。