题解 | #基因变异最小次数#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param start string字符串
     * @param end string字符串
     * @param bank string字符串一维数组
     * @return int整型
     */
    public int minMutation (String start, String end, String[] bank) {
        // write code here
        Set<String> geneBank = new HashSet<>();
        for (String gene : bank) {
            geneBank.add(gene);
        }

        if (!geneBank.contains(end)) {
            return -1; // End gene is not in the gene bank
        }

        char[] charSet = {'A', 'C', 'G', 'T'};
        Set<String> visited = new HashSet<>();
        Set<String> currentLevel = new HashSet<>();
        currentLevel.add(start);
        visited.add(start);

        int mutations = 0;

        while (!currentLevel.isEmpty()) {
            Set<String> nextLevel = new HashSet<>();

            for (String gene : currentLevel) {
                if (gene.equals(end)) {
                    return mutations; // Found the end gene
                }

                char[] geneArray = gene.toCharArray();

                for (int i = 0; i < geneArray.length; i++) {
                    char originalChar = geneArray[i];

                    for (char c : charSet) {
                        geneArray[i] = c;
                        String newGene = new String(geneArray);

                        if (geneBank.contains(newGene) && !visited.contains(newGene)) {
                            nextLevel.add(newGene);
                            visited.add(newGene);
                        }
                    }

                    geneArray[i] = originalChar;
                }
            }

            currentLevel = nextLevel;
            mutations++;
        }

        return -1; // Unable to find a valid mutation
    }
}

知识点：

1. 广度优先搜索（BFS）用于在图中寻找最短路径。
2. 使用 HashSet 可以快速检查元素是否存在，从而提高搜索效率。

解题思路：

首先将基因库中的基因存储在一个 HashSet 中，以便快速地检查一个基因是否有效。然后，我们使用广度优先搜索（BFS）来寻找从起始基因到目标基因的最短变化路径。

我们从起始基因开始，逐层搜索可能的变化，每一层都将当前层的基因变化成可能的下一层基因。我们遍历当前层中的每个基因，将每个字符替换为 A、C、G 和 T 中的一个，生成可能的变化，并检查是否在基因库中。如果在基因库中且未访问过，我们将其添加到下一层，并将其标记为已访问。

我们以这种方式逐步向前搜索，直到找到目标基因或者无法再变化时结束搜索。在搜索过程中，我们使用一个 mutations 变量来记录变化次数。