当前位置： 面试刷题>> 最小基因变化 (经典算法题500道)
### 题目描述补充
**题目：最小基因变化**
给定一个基因序列的开始字符串 `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 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课**网站中有更多关于算法和数据结构的内容分享给大家学习，包括详细解析和更多练习题目，帮助大家深入理解算法思想。