433. Minimum Genetic Mutation LeetCode Solution

In this guide, you will get 433. Minimum Genetic Mutation LeetCode Solution with the best time and space complexity. The solution to Minimum Genetic Mutation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Genetic Mutation solution in C++
Minimum Genetic Mutation solution in Java
Minimum Genetic Mutation solution in Python
Additional Resources

433. Minimum Genetic Mutation LeetCode Solution image

Problem Statement of Minimum Genetic Mutation

A gene string can be represented by an 8-character long string, with choices from ‘A’, ‘C’, ‘G’, and ‘T’.
Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, “AACCGGTT” –> “AACCGGTA” is one mutation.

There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.
Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.
Note that the starting point is assumed to be valid, so it might not be included in the bank.

Example 1:

Input: startGene = “AACCGGTT”, endGene = “AACCGGTA”, bank = [“AACCGGTA”]
Output: 1

Example 2:

Input: startGene = “AACCGGTT”, endGene = “AAACGGTA”, bank = [“AACCGGTA”,”AACCGCTA”,”AAACGGTA”]
Output: 2

Constraints:

0 <= bank.length <= 10
startGene.length == endGene.length == bank[i].length == 8
startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

Complexity Analysis

Time Complexity: O(|\texttt{bank}| \cdot 4^{|\texttt{word}|})
Space Complexity: O(|\texttt{bank}|)

433. Minimum Genetic Mutation LeetCode Solution in C++

class Solution {
 public:
  int minMutation(string startGene, string endGene, vector<string>& bank) {
    unordered_set<string> bankSet{bank.begin(), bank.end()};
    if (!bankSet.contains(endGene))
      return -1;

    constexpr char kGenes[] = "ACGT";
    queue<string> q{{startGene}};

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        string word = q.front();
        q.pop();
        for (int j = 0; j < word.length(); ++j) {
          const char cache = word[j];
          for (const char c : kGenes) {
            word[j] = c;
            if (word == endGene)
              return step;
            if (bankSet.contains(word)) {
              bankSet.erase(word);
              q.push(word);
            }
          }
          word[j] = cache;
        }
      }

    return -1;
  }
};
/* code provided by PROGIEZ */

433. Minimum Genetic Mutation LeetCode Solution in Java

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;

    final char[] kGenes = new char[] {'A', 'C', 'G', 'T'};
    Queue<String> q = new ArrayDeque<>(List.of(startGene));

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        StringBuilder sb = new StringBuilder(q.poll());
        for (int j = 0; j < sb.length(); ++j) {
          final char cache = sb.charAt(j);
          for (final char c : kGenes) {
            sb.setCharAt(j, c);
            final String word = sb.toString();
            if (word.equals(endGene))
              return step;
            if (bankSet.contains(word)) {
              bankSet.remove(word);
              q.offer(word);
            }
          }
          sb.setCharAt(j, cache);
        }
      }

    return -1;
  }
}
// code provided by PROGIEZ

433. Minimum Genetic Mutation LeetCode Solution in Python

class Solution:
  def minMutation(self, startGene: str, endGene: str, bank: list[str]) -> int:
    bankSet = set(bank)
    if endGene not in bankSet:
      return -1

    kGenes = 'ACGT'
    q = collections.deque([startGene])

    step = 1
    while q:
      for _ in range(len(q)):
        wordList = list(q.popleft())
        for j, cache in enumerate(wordList):
          for c in kGenes:
            wordList[j] = c
            word = ''.join(wordList)
            if word == endGene:
              return step
            if word in bankSet:
              bankSet.remove(word)
              q.append(word)
          wordList[j] = cache
      step += 1

    return -1
 # code by PROGIEZ