LeetCode 433: Minimum Genetic Mutation Solution

Master LeetCode problem 433 (Minimum Genetic Mutation), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

433. Minimum Genetic Mutation

Medium

Hash Table String Breadth-First Search

Problem Explanation

Explanation:

To solve this problem, we can use a breadth-first search (BFS) approach. We start with the startGene as the initial state, and we generate all possible valid mutations by changing one character at a time. We keep track of the mutations using a set to avoid duplicates. We continue this process until we find the endGene or exhaust all possible mutations.

Here are the steps:

Create a set bankSet from the bank list for faster lookup.
Initialize a queue with the startGene and a visited set to keep track of visited genes.
Perform BFS by iterating over each gene in the queue:
- Generate all possible mutations for the current gene by changing one character at a time.
- Check if the mutation is in bankSet and not visited before.
- If a valid mutation is found, add it to the queue and mark it as visited.
- Repeat this process until we find the endGene or exhaust all possible mutations.
Return the minimum number of mutations needed or -1 if no valid mutation is found.

Time Complexity: O(N^2 * M), where N is the length of the gene string (8 in this case) and M is the number of genes in the bank. We generate all possible mutations for each gene, which takes O(N) time.

Space Complexity: O(M), where M is the number of genes in the bank for the set bankSet and visited set.

Solution Code

import java.util.*;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        char[] genes = {'A', 'C', 'G', 'T'};
        int mutations = 0;

        queue.offer(startGene);
        visited.add(startGene);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currGene = queue.poll();
                if (currGene.equals(endGene)) {
                    return mutations;
                }

                char[] currArr = currGene.toCharArray();
                for (int j = 0; j < currArr.length; j++) {
                    char originalChar = currArr[j];
                    for (char c : genes) {
                        currArr[j] = c;
                        String newGene = new String(currArr);
                        if (bankSet.contains(newGene) && !visited.contains(newGene)) {
                            queue.offer(newGene);
                            visited.add(newGene);
                        }
                    }
                    currArr[j] = originalChar;
                }
            }
            mutations++;
        }

        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 433 (Minimum Genetic Mutation)?

This page provides optimized solutions for LeetCode problem 433 (Minimum Genetic Mutation) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 433 (Minimum Genetic Mutation)?

The time complexity for LeetCode 433 (Minimum Genetic Mutation) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 433 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 433 in Java, C++, or Python.

Back to LeetCode Solutions