当前位置: 面试刷题>> 最小基因变化(经典算法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 示例代码

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)来记录已访问的基因。

推荐面试题