MediumNo. 0433

Minimum Genetic Mutation — LeetCode 433 Python Solution

Topics
Breadth-First Search, Hash Table, String
On a study list
Top Interview 150
Reading time
3 min

The problem

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.

Example

Input
startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output
1

Python solution

PythonSolution
class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        q = deque([(startGene, 0)])
        vis = {startGene}
        while q:
            gene, depth = q.popleft()
            if gene == endGene:
                return depth
            for nxt in bank:
                diff = sum(a != b for a, b in zip(gene, nxt))
                if diff == 1 and nxt not in vis:
                    q.append((nxt, depth + 1))
                    vis.add(nxt)
        return -1

Complexity

Time
O(C × n × m)
Space · auxiliary
O(n × m)

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 433. Minimum Genetic Mutation is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0126Word Ladder IIHard
0127Word LadderHard
0721Accounts MergeMedium
0752Open the LockMedium
0839Similar String GroupsHard
0854K-Similar StringsHard

Frequently asked questions

How hard is LeetCode 433. Minimum Genetic Mutation?

LeetCode 433. Minimum Genetic Mutation is rated Medium on LeetCode.

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

The Python solution on this page runs in O(C × n × m).

What is the space complexity of LeetCode 433. Minimum Genetic Mutation?

The Python solution on this page uses O(n × m) auxiliary space.

What topics does LeetCode 433. Minimum Genetic Mutation cover?

LeetCode 433. Minimum Genetic Mutation is tagged Breadth-First Search, Hash Table and String on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.