433 最小基因变化

题目描述#

基因序列由 8 个字符组成，每个字符是 'A'、'C'、'G'、'T' 之一。一次基因变化指序列中恰好一个字符发生变化，且变化后的序列必须出现在基因库 bank 中。

给你起点 startGene、终点 endGene 和基因库 bank，求从 startGene 变到 endGene 所需的最少变化次数；不可达返回 -1。startGene 默认有效，但不必出现在 bank 中。

思路#

把每个基因序列看作图中的一个节点，两个序列若仅相差一个字符则连一条边。问题就转化为在这张无权图上求 startGene 到 endGene 的最短路径——典型的 BFS 应用。

不需要预先建图，只需在 BFS 扩展时枚举邻居即可：对当前序列的 8 个位置依次尝试替换为 A/C/G/T 中其余 3 种字符，得到 24 个候选；候选若等于 endGene，直接返回当前层数；否则只有当它在 bank 中且未访问过时才入队。

层序 BFS 的写法保证「第一次访问到 endGene」就是最短距离，每处理完一层 ans++。提前判断 endGene 是否在 bank 中可以快速剪掉无解情况。

知识边界#

字符串"差一字符"问题（127 单词接龙同款套路）：状态空间小、字符集有限时，不建图、按位枚举邻居比预先建图更省事
基因长度固定为 8，字符集为 4，每层每个节点最多扩展 8 × 3 = 24 个邻居，整体复杂度可控
visited 标记必须在入队时打上而非出队时，否则同一节点可能被多个父节点重复入队
起点 startGene 不一定在 bank 中，但终点 endGene 必须在 bank 中——否则任何路径都无法走通

代码#

func minMutation(startGene string, endGene string, bank []string) int {
    // 0. 建立一个集合方便查找
    bankSet := make(map[string]bool)
    for _, v := range bank {
        bankSet[v] = true
    }
    if bankSet[endGene] == false {
        return -1
    }

    // 1. 准备广度搜索的条件
    queue := []string{startGene}
    visited := make(map[string]bool)
    ans := 0
    genes := []byte{'A', 'C', 'G', 'T'}

    for len(queue) > 0 {
        ans++
        // 生成当前的状态快照
        size := len(queue)
        for i := 0; i < size; i++ {
            // 获得当前的基因
            cur := queue[i]
            // 遍历当前基因
            for j := 0; j < len(cur); j++ {
                // 编辑基因组，找到需要的基因
                for _, v := range genes {
                    // 如果遍历的基因和当前cur的基因一样则跳过
                    if v == cur[j] {
                        continue
                    }
                    nextString := []byte(cur)
                    nextString[j] = v
                    // 这个nextStr就是下一个变换的基因
                    nextStr := string(nextString)
                    // 如果下一个基因和end基因一致，则返回
                    if nextStr == endGene {
                        return ans
                    }
                    // 如果不是最终基因，则对比基因库和查看之前是否访问过
                    if bankSet[nextStr] && visited[nextStr] == false {
                        visited[nextStr] = true
                        queue = append(queue, nextStr)
                    }
                }

            }
        }
        // 当前基因已经消费完毕，进入下一个基因
        queue = queue[size:]
    }
    return -1
}