题目描述

最小基因变化

给定一个基因字符串 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）来记录已访问的基因。