MediumNo. 0433
Minimum Genetic Mutation — LeetCode 433 Python Solution
- Pattern
- Breadth-First Search
- Topics
- Breadth-First Search, Hash Table, String
- On a study list
- Top Interview 150
- Reading time
- 3 min
- Source
- leetcode.com
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
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 -1Complexity
- 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
| No. | Problem | Difficulty |
|---|---|---|
| 0126 | Word Ladder II | Hard |
| 0127 | Word Ladder | Hard |
| 0721 | Accounts Merge | Medium |
| 0752 | Open the Lock | Medium |
| 0839 | Similar String Groups | Hard |
| 0854 | K-Similar Strings | Hard |
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.