248. Minimum Genetic Mutation

Each valid gene is a graph node; two genes are connected if they differ by exactly one character. The minimum number of mutations is the shortest path from startGene to endGene, which BFS finds level by level.

Idea

Think of every gene string as a node. An edge connects two genes that differ in exactly one character — a single mutation. The answer is the shortest path from startGene to endGene through valid genes (those in the bank). BFS explores outward one mutation at a time, so the first time we reach endGene we've used the fewest mutations.

Algorithm

1. Put the bank in a set for O(1) validity checks. If endGene isn't in it, return -1.
2. BFS from startGene at distance 0, tracking visited genes.
3. To expand a gene, try changing each of its 8 positions to each of A/C/G/T. If the result is in the bank and unvisited, enqueue it at distance +1.
4. Return the distance when endGene is dequeued; -1 if BFS finishes without reaching it.

Worked example

start = "AACCGGTT", end = "AAACGGTA", bank ["AACCGGTA","AACCGCTA","AAACGGTA"]:

• AACCGGTT → AACCGGTA (1).
• AACCGGTA → AAACGGTA (2).

Answer: 2.

Complexity

• Time: O(B · L · 4) where B is the bank size and L the gene length (8).
• Space: O(B) for the visited set and queue.

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        if (!bankSet.contains(endGene)) {
            return -1;
        }
        Set<String> seen = new HashSet<>();
        seen.add(startGene);
        Queue<String> q = new LinkedList<>();
        q.offer(startGene);
        char[] choices = {'A', 'C', 'G', 'T'};
        int steps = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int s = 0; s < size; s++) {
                String gene = q.poll();
                if (gene.equals(endGene)) {
                    return steps;
                }
                char[] arr = gene.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    char original = arr[i];
                    for (char c : choices) {
                        if (c != original) {
                            arr[i] = c;
                            String mutated = new String(arr);
                            if (bankSet.contains(mutated) && !seen.contains(mutated)) {
                                seen.add(mutated);
                                q.offer(mutated);
                            }
                        }
                    }
                    arr[i] = original;
                }
            }
            steps++;
        }
        return -1;
    }
}