题目描述补充

题目：最小基因变化

给定一个基因序列的开始字符串 start 和一个目标字符串 end，以及一个字符串数组 bank，其中 bank[i] 表示可能的基因变异序列。一个基因序列可以通过一个字符的变化（替换）变成另一个基因序列（即一次变异）。

编写一个函数来找出从 start 到 end 所需的最少变异次数。如果不可能从 start 变异到 end，则返回 -1。

注意：

1. 所有的基因序列都由小写字母组成，且长度相同。
2. 你可以假设 start 和 end 是非空的，且只包含小写字母。
3. bank 数组中的字符串都是唯一的。
4. 你可以假设 start 不在 bank 数组中。

示例

输入:

start = "AACCGGTT"
end = "AACCGGTA"
bank = ["AACCGGTA"]

输出: 1

解释: 可以通过将第7个字符从 'T' 变为 'A' 来从 "AACCGGTT" 变异到 "AACCGGTA"。

PHP 示例代码

function minMutation($start, $end, $bank) {
    if (!in_array($end, $bank)) return -1;
    
    $queue = new SplQueue();
    $queue->enqueue([$start, 0]); // [当前字符串, 变异次数]
    $visited = array_fill_keys($bank, false);
    $visited[$start] = true;
    
    while (!$queue->isEmpty()) {
        [$current, $steps] = $queue->dequeue();
        
        if ($current == $end) {
            return $steps;
        }
        
        for ($i = 0; $i < strlen($current); $i++) {
            $originalChar = $current[$i];
            for ($j = 0; $j < 26; $j++) {
                $newChar = chr(ord('a') + $j);
                if ($originalChar == $newChar) continue;
                
                $newString = substr_replace($current, $newChar, $i, 1);
                if (!isset($visited[$newString]) && in_array($newString, $bank)) {
                    $visited[$newString] = true;
                    $queue->enqueue([$newString, $steps + 1]);
                }
            }
        }
    }
    
    return -1;
}

// 示例用法
$start = "AACCGGTT";
$end = "AACCGGTA";
$bank = ["AACCGGTA"];
echo minMutation($start, $end, $bank); // 输出: 1

Python 示例代码

from collections import deque

def minMutation(start, end, bank):
    if end not in bank:
        return -1
    
    queue = deque([(start, 0)])
    visited = set(bank)
    visited.remove(start)
    
    while queue:
        current, steps = queue.popleft()
        
        if current == end:
            return steps
        
        for i in range(len(current)):
            original_char = current[i]
            for new_char in 'abcdefghijklmnopqrstuvwxyz':
                if new_char == original_char:
                    continue
                
                new_string = current[:i] + new_char + current[i+1:]
                if new_string in visited:
                    visited.remove(new_string)
                    queue.append((new_string, steps + 1))
    
    return -1

# 示例用法
start = "AACCGGTT"
end = "AACCGGTA"
bank = ["AACCGGTA"]
print(minMutation(start, end, bank))  # 输出: 1

JavaScript 示例代码

function minMutation(start, end, bank) {
    if (!bank.includes(end)) return -1;
    
    const queue = [[start, 0]];
    const visited = new Set(bank);
    visited.delete(start);
    
    while (queue.length > 0) {
        const [current, steps] = queue.shift();
        
        if (current === end) {
            return steps;
        }
        
        for (let i = 0; i < current.length; i++) {
            const originalChar = current[i];
            for (let j = 0; j < 26; j++) {
                const newChar = String.fromCharCode(97 + j);
                if (originalChar === newChar) continue;
                
                const newString = current.substring(0, i) + newChar + current.substring(i + 1);
                if (visited.has(newString)) {
                    visited.delete(newString);
                    queue.push([newString, steps + 1]);
                }
            }
        }
    }
    
    return -1;
}

// 示例用法
const start = "AACCGGTT";
const end = "AACCGGTA";
const bank = ["AACCGGTA"];
console.log(minMutation(start, end, bank)); // 输出: 1

码小课网站中有更多关于算法和数据结构的内容分享给大家学习，包括详细解析和更多练习题目，帮助大家深入理解算法思想。