C++ 中的最小基因突变

问题描述

此问题中的起始基因字符串和结束基因字符串都由八个字符组成，并且由字母“A”、“C”、“G”和“T”构成。此外，我们还有一个合法的基因突变库。一个基因必须存在于该库中，才能被视为有效突变。突变定义为基因字符串中单个字符的改变。

当前的任务是找到将起始基因转化为结束基因所需的最少突变。如果无法仅使用库中的合法突变从起始基因到达结束基因，我们必须返回 -1。重要的是要记住，起始基因之后的每个步骤都必须涉及库中存在的突变；即使起始基因不存在，它也是有效的。

基因字符串突变是潜在字符集中单个字符的改变。例如，**_‘AACCGGTT’_** 变为 **_‘AACCGGTA’_** 是一种突变。

直觉

• 可以使用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 来解决此问题。但是，BFS 更适合确定无权图中的最短路径，这类似于确定所需的最少突变。
• 该解决方案的基本思想是将每个基因字符串视为图的节点，并将每个合法突变视为连接两个节点的边。
• 使用 BFS，我们逐层检查图，从起始基因到结束基因。
• 由于 BFS 确定从起始节点到结束节点的最短路径（最少突变），因此它非常适合这种情况。

BFS 的关键步骤如下：

1. 首先，从库中初始化一个集合，以快速确定突变是否合法。
2. 启动一个队列，其中包含已初始化的起始基因和突变计数为 0。
3. 之后，检查字典以确定每个字符的潜在突变。出队一个元素，然后遍历其字符，根据突变的可能性单独更改每个字符。
4. 如果新突变合法（在库中），则将其入队，计数加一。
5. 如果我们到达最后一个基因，则返回突变数量。
6. 如果队列已满但未找到最后一个基因，则返回 -1。
7. 通过应用此 BFS 方法，我们以最少的步骤探索每个潜在的基因突变，如果可行，确保达到目标基因所需的最少突变。

解决方法

解决方案中使用的算法，称为**_广度优先搜索 (BFS)_**，用于搜索或遍历树或图数据结构。在进入下一深度级别的节点之前，它会调查当前深度级别的相邻节点。实现中包含以下数据结构、算法和模式：

Set

• 集合的初始化来自库，在确定基因字符串是否存在时提供 O(1) 的复杂度。

队列（双端队列）

• 使用由双端队列数据结构组成的队列来实现 BFS。对象在一端附加，在另一端移除，模拟队列的先进先出 (FIFO) 特性。

哈希图

• 为了显示单个字符的潜在变体，字典 MP 将每个字符绑定到其他三个字符。这使得在任何给定点确定基因字符串的突变是否可行变得简单。

图的逐层遍历

• 该算法逐层遍历图。它使用 BFS 方法对其进行检查，将所有可从当前基因字符串通过单个突变访问的基因字符串视为邻居。

提前停止

• 如果在探索过程中发现了结束基因，则该函数会立即返回达到此状态所需的突变（步骤）数量。

图剪枝

• 每当在库中发现新的、有效的基因字符串时，都会将其从集合中删除，以防止基因字符串被重新访问，从而陷入循环。这保证了每个基因字符串只访问一次。

示例

让我们举一个例子来说明 C++ 中的最小基因突变。

输出