当前位置： 面试刷题>> 最小基因变化(经典算法150题)
### 题目描述
**最小基因变化**
给定一个基因字符串 `startGene` 表示起始基因，一个字符串数组 `targetGenes` 表示目标基因集合，以及一个字符串 `bank` 表示基因库（即所有可能的基因变异字符串）。基因字符串仅由 `'A'`, `'C'`, `'G'`, `'T'` 这四个字符组成。
基因可以通过一次变异从一个基因变为另一个基因，变异指的是将一个字符替换为基因库中的任意一个字符。请找出从起始基因 `startGene` 到目标基因集合 `targetGenes` 中的某个基因所需的最少变异次数。如果没有可能到达目标基因集合，则返回 `-1`。
**示例 1**:
```
输入: startGene = "AACCGGTT", targetGenes = ["AACCGGTA"], bank = ["AACCGGTA"]
输出: 1
解释: 起始基因可以通过一次变异得到目标基因 "AACCGGTA"。
```
**示例 2**:
```
输入: startGene = "AACCGGTT", targetGenes = ["AAACGGTA","AACCGCTA","AAACGGTA"], bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出: 2
解释: 可以通过两次变异从起始基因得到第一个或第三个目标基因。
```
**示例 3**:
```
输入: startGene = "AAAA", targetGenes = ["AAAA"], bank = ["AAAA"]
输出: 0
解释: 起始基因和目标基因相同，无需变异。
```
### 解题思路
这是一个图搜索问题，可以使用广度优先搜索（BFS）算法来解决。我们可以将基因视为图中的节点，如果两个基因只相差一个字符，则它们之间存在一条边。起始基因是起点，目标基因集合中的基因是终点。
1. **初始化**：创建一个队列用于BFS，将起始基因和变异次数0一起入队。同时，使用一个集合来记录已经访问过的基因，避免重复访问。
2. **BFS遍历**：在遍历过程中，对于队列中的每个基因，尝试将其每个字符替换为基因库中的其他字符，生成所有可能的变异基因。如果某个变异基因存在于目标基因集合中，则返回当前的变异次数。如果变异基因尚未被访问过，则将其加入队列和已访问集合中，并继续搜索。
3. **结束条件**：如果队列为空时仍未找到目标基因，则返回-1。
### PHP 示例代码
```php
function minMutation($startGene, $targetGenes, $bank) {
$visited = array_flip($bank); // 使用数组翻转作为集合，快速查找
$queue = new SplQueue();
$queue->enqueue([$startGene, 0]); // [基因, 变异次数]
while (!$queue->isEmpty()) {
[$gene, $steps] = $queue->dequeue();
if (in_array($gene, $targetGenes)) {
return $steps;
}
for ($i = 0; $i < strlen($gene); $i++) {
$originalChar = $gene[$i];
for ($j = 0; $j < strlen('ACGT'); $j++) {
$newChar = 'ACGT'[$j];
if ($newChar != $originalChar) {
$newGene = substr_replace($gene, $newChar, $i, 1);
if (isset($visited[$newGene])) {
unset($visited[$newGene]); // 标记为已访问
$queue->enqueue([$newGene, $steps + 1]);
}
}
}
}
}
return -1;
}
```
注意：由于PHP标准库中没有直接的队列实现，这里使用了`SplQueue`。另外，`$visited`数组通过`array_flip`初始化为基因库的反向索引，以快速检查一个基因是否已访问过。
### Python 和 JavaScript 示例代码
由于篇幅限制，这里不再重复展示完整的Python和JavaScript代码，但它们的实现思路与PHP类似，只是语法和库的使用有所不同。Python可以使用`collections.deque`作为队列，JavaScript可以使用数组模拟队列操作。同时，它们也都会使用集合（Python的`set`，JavaScript的`Set`）来记录已访问的基因。