433. Minimum Genetic Mutation

Description

The goal is to determine the minimum number of mutations required to transform a startGene into an endGene using a set of allowed mutations provided in the bank. Each mutation involves changing a single character in the gene string. If the transformation is not possible, return -1.

Intuition

The problem can be approached using Breadth-First Search (BFS) because it involves finding the shortest path (minimum mutations) in an unweighted graph where each gene is a node and edges exist between nodes that can be reached by a single mutation.

Approach

1. Convert the bank list into a set for O(1) lookup times.
2. Use a queue to implement BFS, starting with the startGene.
3. Track the number of mutations required.
4. For each gene in the queue, generate all possible single mutations.
5. If a mutated gene is in the bank, add it to the queue and remove it from the bank.
6. If the endGene is found, return the number of mutations.
7. If the queue is exhausted without finding the endGene, return -1.

Complexity

Time Complexity:

O(N * L^2), where N is the number of genes in the bank and L is the length of each gene. For each gene, we generate all possible mutations (L) and check if they are in the bank (L).

Space Complexity:

O(N * L), where N is the number of genes and L is the length of each gene. The space is used for the queue and the bank set.

Code

C++

class Solution {
public:
    int minMutation(string startGene, string endGene, vector& bank) {
        unordered_set bankSet(bank.begin(), bank.end());
        queue q;
        q.push(startGene);
        int ans = 1;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                string gene = q.front();
                q.pop();

                for (auto it = bankSet.begin(); it != bankSet.end(); ) {
                    string b = *it;
                    int diff = 0;
                    for (int j = 0; j < 8 && diff < 2; ++j) {
                        diff += (gene[j] == b[j]) ? 0 : 1;
                    }

                    if (diff == 1) {
                        if (b == endGene) {
                            return ans;
                        }
                        q.push(b);
                        it = bankSet.erase(it);
                    } else {
                        ++it;
                    }
                }
            }
            ++ans;
        }
        return -1;
    }
};

Python

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        bankSet = set(bank)
        if endGene not in bankSet:
            return -1
        
        queue = deque([startGene])
        mutations = 0
        
        while queue:
            for _ in range(len(queue)):
                gene = queue.popleft()
                if gene == endGene:
                    return mutations
                
                for i in range(len(gene)):
                    for c in "ACGT":
                        mutated = gene[:i] + c + gene[i+1:]
                        if mutated in bankSet:
                            queue.append(mutated)
                            bankSet.remove(mutated)
            
            mutations += 1
        
        return -1

Java

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set bankSet = new HashSet<>(Arrays.asList(bank));
        Queue q = new LinkedList<>();
        q.offer(startGene);
        int ans = 1;

        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String gene = q.poll();

                Iterator it = bankSet.iterator();
                while (it.hasNext()) {
                    String b = it.next();
                    int diff = 0;
                    for (int j = 0; j < 8 && diff < 2; j++) {
                        if (gene.charAt(j) != b.charAt(j)) {
                            diff++;
                        }
                    }
                    if (diff == 1) {
                        if (b.equals(endGene)) {
                            return ans;
                        }
                        q.offer(b);
                        it.remove();
                    }
                }
            }
            ans++;
        }
        return -1;
    }
}

JavaScript

var minMutation = function(startGene, endGene, bank) {
    const bankSet = new Set(bank);
    let q = [startGene];
    let ans = 1;
    while (q.length > 0) {
        let nextQ = [];
        for (const gene of q) {
            for (const b of bankSet.values()) {
                let diff = 0;
                for (let i = 0; i < 8 && diff < 2; i++) {
                    diff += gene[i] === b[i] ? 0 : 1;
                }
                if (diff === 1) {
                    if (b === endGene) {
                        return ans;
                    }
                    nextQ.push(b);
                    bankSet.delete(b);
                }
            }
        }
        ans++;
        q = nextQ;
    }
    return -1;
};