algoadvance

Leetcode 433. Minimum Genetic Mutation

Problem Statement

A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T". To change one gene string into another, you can mutate one character at a time. Each mutation must change one character into a different character.

You need to determine the minimum number of mutations needed to transform the start gene string into the end gene string. If there is no possible mutation path to transform the start string into the end string, return -1.

Note that intermediate gene strings must be valid gene strings in the bank.

Example:

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

Input: start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
Output: 3

Constraints:

Clarifying Questions

  1. Can we assume that the start and end strings, as well as all strings in the bank, contain only the characters "A", "C", "G", and "T"?
  2. Is there a guaranteed start and end string provided for all test cases?
  3. Is the gene bank guaranteed to be free of duplicates, or do I need to handle potential duplicates?

Let’s assume the answers to the above questions are as follows:

  1. Yes.
  2. Yes.
  3. The bank is guaranteed to be free of duplicates.

Strategy

To solve this problem, a Breadth-First Search (BFS) approach is most suitable. This is because BFS is great for finding the shortest path in an unweighted graph, which matches our goal of finding the minimum number of mutations.

Here are the steps we’ll take:

  1. If the end gene is not in the bank, return -1 because it’s impossible to reach the end.
  2. Initialize a queue and add the start gene.
  3. Initialize a set to keep track of visited gene mutations to avoid cycles.
  4. While the queue is not empty:
    • For each gene in the queue, generate all possible valid mutations that are one character different and are present in the bank.
    • If a valid mutation matches the end gene, return the number of mutations.
    • Otherwise, add the mutation to the queue and mark it as visited.
  5. If the end gene is never reached, return -1.

Code

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

public class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Set<String> bankSet = new HashSet<>(); 
        for (String gene : bank) {
            bankSet.add(gene);
        }
        
        if (!bankSet.contains(end)) {
            return -1;
        }
        
        char[] charSet = new char[]{'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        Set<String> visited = new HashSet<>();
        visited.add(start);
        
        int level = 0;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                String current = queue.poll();
                if (current.equals(end)) {
                    return level;
                }
                
                char[] currentArray = current.toCharArray();
                for (int i = 0; i < currentArray.length; i++) {
                    char originalChar = currentArray[i];
                    for (char c : charSet) {
                        if (c != originalChar) {
                            currentArray[i] = c;
                            String mutatedGene = new String(currentArray);
                            if (bankSet.contains(mutatedGene) && !visited.contains(mutatedGene)) {
                                queue.offer(mutatedGene);
                                visited.add(mutatedGene);
                            }
                        }
                    }
                    currentArray[i] = originalChar;
                }
            }
            level++;
        }
        
        return -1;
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI