< Back




433. Minimum Genetic Mutation

Fun question. We're asked to mutate some genes, given a starting string that contains characters
"A", "C", "G", and "T". We're asked to find the number of steps we need to take to get to the target
mutation. We're also provided with a bank of valid mutations.

This is classic BFS problem. We start by creating a matrix of valid state transitions for each gene
character. Then we conduct our regular BFS with a queue. If the current node is the target gene, we
return the number of steps we've taken so far. Otherwise, for each character in the current node,
we check its valid mutations (neighbors) using the matrix we created previously. If the mutation is
in the bank and not seen, we mark it as visited and add it to the queue to process in the next step.

We continue the BFS until we find the target, otherwise we return -1.

The solution is as follows:


  class Solution:
      def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
          mutations = {
              "A": ["C", "G", "T"],
              "C": ["G", "T", "A"],
              "G": ["T", "A", "C"],
              "T": ["A", "C", "G"],
          }

          seen = {startGene}
          queue = [(startGene, 0)]

          while queue:
              curr_queue, queue = queue, []

              for node, steps in curr_queue:
                  if node == endGene:
                      return steps

                  for i in range(8):
                      for c in mutations[node[i]]:
                          mutation = node[:i] + c + node[i + 1 :]

                          if mutation in bank and mutation not in seen:
                              seen.add(mutation)
                              queue.append((mutation, steps + 1))

          return -1


_ Time Complexity:

  O(b) - Where b is the length of the bank. The BFS runs in constant time because the length of the
  nodes is 8 and the number of genes is 4.

_ Space Complexity:

  O(1) - We technically use constant space.