LeetCode 433. 最小基因变化

Categories:

题目描述
思路分析
1. 解法一：BFS 最短路径（推荐）
相似题目

题目描述

✅ 433. 最小基因变化

思路分析

解法一：BFS 最短路径（推荐）

核心思路：

将基因看作图中的节点，单字符变换且在基因库内的为边。

BFS 从 start 出发，首次到达 end 即最少变换次数。

每次尝试替换 8 个位置为 A/C/G/T 生成相邻节点。

复杂度分析：

时间复杂度：O(B _ L _ 4)，其中 B 为基因库大小，L 为基因长度。

空间复杂度：O(B)，用于队列与访问集合。

import java.util.*;

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Set<String> dict = new HashSet<>(Arrays.asList(bank));
        if (!dict.contains(end)) {
            return -1;
        }

        char[] genes = {'A', 'C', 'G', 'T'};
        Deque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();

        queue.offer(start);
        visited.add(start);
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(end)) {
                    return steps;
                }

                char[] arr = cur.toCharArray();
                for (int p = 0; p < arr.length; p++) {
                    char old = arr[p];
                    for (char g : genes) {
                        if (g == old) {
                            continue;
                        }
                        arr[p] = g;
                        String next = new String(arr);
                        if (dict.contains(next) && visited.add(next)) {
                            queue.offer(next);
                        }
                    }
                    arr[p] = old;
                }
            }
            steps++;
        }

        return -1;
    }
}

func minMutation(start string, end string, bank []string) int {
    dict := make(map[string]struct{})
    for _, b := range bank {
        dict[b] = struct{}{}
    }
    if _, ok := dict[end]; !ok {
        return -1
    }

    genes := []byte{'A', 'C', 'G', 'T'}
    queue := []string{start}
    visited := map[string]struct{}{start: {}}
    steps := 0

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            cur := queue[0]
            queue = queue[1:]

            if cur == end {
                return steps
            }

            arr := []byte(cur)
            for p := 0; p < len(arr); p++ {
                old := arr[p]
                for _, g := range genes {
                    if g == old {
                        continue
                    }
                    arr[p] = g
                    next := string(arr)
                    if _, ok := dict[next]; ok {
                        if _, seen := visited[next]; !seen {
                            visited[next] = struct{}{}
                            queue = append(queue, next)
                        }
                    }
                }
                arr[p] = old
            }
        }
        steps++
    }

    return -1
}

相似题目

题目	难度	考察点
127. 单词接龙	困难	BFS
126. 单词接龙 II	困难	BFS
752. 打开转盘锁	中等	BFS
847. 访问所有节点的最短路径	困难	BFS
994. 腐烂的橘子	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/44549667