当前位置：首页 > article >正文

LeetCode题练习与总结：最小基因变化--433

article 2024/12/27 10:34:16

一、题目描述

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1

示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2

示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

提示：

start.length == 8
end.length == 8
0 <= bank.length <= 10
bank[i].length == 8
start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成

二、解题思路

这个问题可以看作是一个无向图的最短路径问题，其中每个基因序列是一个节点，如果两个基因序列之间只有一个字符不同，那么这两个节点之间有一条边。我们的目标是找到从起点基因序列到终点基因序列的最短路径。

以下是解题步骤：

创建一个集合（或使用布尔数组）来记录基因库中哪些基因序列已经被使用过，以避免重复访问。
使用一个队列来进行广度优先搜索（BFS）。初始时，将起点基因序列放入队列中。
在队列不为空的情况下，进行以下操作：
- 从队列中取出一个基因序列。
- 如果这个基因序列与终点基因序列相同，返回当前的变化次数。
- 否则，遍历基因库中的每个基因序列，检查是否只有一个字符不同，并且该基因序列没有被使用过。如果是，将其加入队列，并标记为已使用。
如果队列为空还没有找到终点基因序列，返回 -1。

三、具体代码

import java.util.*;

public class Solution {
    public int minMutation(String start, String end, String[] bank) {
        // 使用集合来记录已经使用过的基因序列
        Set<String> visited = new HashSet<>();
        // 使用队列进行广度优先搜索
        Queue<String> queue = new LinkedList<>();
        // 初始化队列和访问集合
        queue.offer(start);
        visited.add(start);
        // 变化次数
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历当前层的所有节点
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                // 如果当前节点与终点相同，返回变化次数
                if (current.equals(end)) {
                    return steps;
                }
                // 遍历基因库中的每个基因序列
                for (String gene : bank) {
                    // 如果基因序列没有被使用过，并且只有一个字符不同
                    if (!visited.contains(gene) && isMutation(current, gene)) {
                        queue.offer(gene);
                        visited.add(gene);
                    }
                }
            }
            // 增加变化次数
            steps++;
        }
        // 如果无法完成变化，返回 -1
        return -1;
    }

    // 检查两个基因序列是否只有一个字符不同
    private boolean isMutation(String start, String end) {
        int diff = 0;
        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) != end.charAt(i)) {
                diff++;
                if (diff > 1) {
                    return false;
                }
            }
        }
        return diff == 1;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化阶段，将起始基因序列 start 加入队列，这一步的时间复杂度是 O(1)。
在广度优先搜索（BFS）过程中，我们遍历队列中的每个元素，并对每个元素检查基因库中的所有基因序列。假设基因库的大小为 n，那么在每层BFS中，我们需要检查 n 个基因序列，并且对于每个基因序列，我们执行 isMutation 方法来检查是否只有一个字符不同，isMutation 方法的时间复杂度是 O(8)，因为每个基因序列的长度是固定的 8。
BFS 可能会遍历所有 n 个基因序列，因为最坏情况下每个基因序列都可能被加入到队列中。因此，队列的大小最多可能是 n。

综合以上分析，总的时间复杂度是 O(n^2 * 8)，可以简化为 O(n^2)，因为 8 是一个常数。

2. 空间复杂度

visited 集合用于存储已经访问过的基因序列，最坏情况下需要存储 n 个基因序列，因此空间复杂度是 O(n)。
队列 queue 在最坏情况下可能包含所有 n 个基因序列，因此空间复杂度也是 O(n)。

综合以上分析，总的空间复杂度是 O(n) + O(n)，可以简化为 O(n)，因为两个 O(n) 是同阶的。

五、总结知识点

面向对象编程（OOP）：
- 类定义（public class Solution）。
- 方法定义（public int minMutation(...) 和 private boolean isMutation(...)）。
数据结构：
- 集合（Set<String>）：用于存储已经访问过的基因序列，确保不会重复访问。
- 队列（Queue<String>）：用于实现广度优先搜索（BFS）。
算法：
- 广度优先搜索（BFS）：用于在无向图中找到从起点到终点的最短路径。
- 字符串比较：用于判断两个基因序列是否只有一个字符不同。
字符串操作：
- 使用 charAt(int index) 方法获取字符串中指定位置的字符。
- 使用 equals(Object anObject) 方法比较两个字符串是否相等。
控制结构：
- 循环结构：for 循环用于遍历队列中的元素和字符串中的字符。
- 条件语句：if 语句用于检查条件是否满足，并据此执行不同的操作。
集合操作：
- 使用 add(E e) 方法向集合中添加元素。
- 使用 contains(Object o) 方法检查集合中是否包含特定的元素。
队列操作：
- 使用 offer(E e) 方法向队列中添加元素。
- 使用 poll() 方法从队列中取出并移除头部元素。
- 使用 size() 方法获取队列中的元素数量。
错误处理：
- 如果无法从起始基因序列变换到目标基因序列，则返回 -1。