leetcode433：最小基因变化

基因序列可以表示为一条由 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'] 组成

class Solution {
public:
    // 判断两个基因序列是否只相差一个字符
bool isOneMutationAway(const string &a, const string &b) {
    int diff = 0;
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] != b[i]) {
            ++diff;
            if (diff > 1) return false;
        }
    }
    return diff == 1;
}

int minMutation(string start, string end, vector<string> &bank) {
    // 将基因库存入集合以便快速查找
    unordered_set<string> bankSet(bank.begin(), bank.end());
    if (bankSet.find(end) == bankSet.end()) return -1; // 如果end不在基因库中，返回-1

    // 广度优先搜索
    queue<pair<string, int>> q;
    q.push({start, 0}); // 起点入队，变化次数为0
    unordered_set<string> visited; // 记录访问过的序列
    visited.insert(start);

    while (!q.empty()) {
        auto [current, mutations] = q.front();
        q.pop();

        // 如果到达目标序列，返回变化次数
        if (current == end) return mutations;

        // 遍历基因库中的所有序列
        for (const string &gene : bank) {
            if (visited.find(gene) == visited.end() && isOneMutationAway(current, gene)) {
                q.push({gene, mutations + 1});
                visited.insert(gene);
            }
        }
    }

    // 如果无法到达目标序列，返回-1
    return -1;
}
};

步骤4：启发

1. 问题抽象：现实问题往往可以建模为图论问题，通过搜索算法解决最优路径问题。
2. 算法选型：对于最短路径问题，BFS是直接且高效的选择。
3. 边界处理：预处理和条件检查可以大幅减少不必要的计算量。

步骤5：实际生活中的应用

实际应用领域
基因序列的变化模拟在生物信息学中有广泛的应用，尤其是在研究基因突变、进化树构建以及遗传病检测中。

应用示例

• 新冠病毒变异分析：
  • 目标：追踪病毒基因序列的变异路径，确定变异来源。
  • 实现方法：将每个病毒基因组视为一个节点，使用类似的算法计算最短突变路径，从而分析变异传播链。