题目描述
最小基因变化
给定一个基因字符串 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)算法来解决。我们可以将基因视为图中的节点,如果两个基因只相差一个字符,则它们之间存在一条边。起始基因是起点,目标基因集合中的基因是终点。
- 初始化:创建一个队列用于BFS,将起始基因和变异次数0一起入队。同时,使用一个集合来记录已经访问过的基因,避免重复访问。
- BFS遍历:在遍历过程中,对于队列中的每个基因,尝试将其每个字符替换为基因库中的其他字符,生成所有可能的变异基因。如果某个变异基因存在于目标基因集合中,则返回当前的变异次数。如果变异基因尚未被访问过,则将其加入队列和已访问集合中,并继续搜索。
- 结束条件:如果队列为空时仍未找到目标基因,则返回-1。
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
)来记录已访问的基因。