LeetCode #433 Medium

Minimum Genetic Mutation

Find the minimum number of single-gene mutations to turn startGene into endGene, only passing through genes in bank.

bfsimplicit-graphstrings

Open on LeetCode ↗

02

Intuition

This looks like a string-edit-distance problem, but treating it that way misses the actual constraint: every intermediate gene must exist in bank, and the alphabet is fixed to just A, C, G, T. It is exactly the same BFS as Word Ladder, generating one-letter-swap neighbors on demand, just with 4 letters instead of 26. The trap that catches people fastest is forgetting to check that endGene is even in the bank first - no matter how close a string looks to endGene, if it never appears in bank, it can never be a legal stop on the mutation path, so the answer is -1 regardless of edit distance.

How to spot this pattern

Word Ladder with a four-letter alphabet — ACGT instead of a–z, and a bank instead of a word list. Recognising the two problems as identical means the second one costs no new thinking, only a change of constants.

03

Approach

1

Guard the target

If endGene is not present in bank, it is unreachable no matter what, so return -1 immediately.

2

Generate neighbors over 4 letters

From the current gene, try each position with each of A/C/G/T (skipping the existing letter). A candidate is a valid neighbor exactly when it is in bank and not yet visited.

3

BFS layer = mutation count

Track mutation count from startGene (0 mutations). The first time endGene is generated, that count is the minimum, since BFS finds shortest paths first.

04

Solution & live demo

▶1class Solution:
▶2    def minMutation(self, startGene, endGene, bank):
▶3        from collections import deque
▶4        bankSet = set(bank)
▶5        if endGene not in bankSet:
▶6            return -1
▶7        q = deque([(startGene, 0)])
▶8        visited = {startGene}
▶9        while q:
▶10            gene, d = q.popleft()
▶11            if gene == endGene:
▶12                return d
▶13            for i in range(len(gene)):
▶14                for ch in 'ACGT':
▶15                    if ch == gene[i]:
▶16                        continue
▶17                    cand = gene[:i] + ch + gene[i+1:]
▶18                    if cand in bankSet and cand not in visited:
▶19                        visited.add(cand)
▶20                        q.append((cand, d+1))
▶21        return -1

05

Common pitfalls

Allowing the unchanged character

✗ Wrong

for ch in 'ACGT':
    cand = gene[:i] + ch + gene[i+1:]

✓ Right

if ch == gene[i]:
    continue

Substituting a character with itself produces the current gene, which is already visited — harmless with a visited check, but it wastes a set lookup on every position and obscures that a mutation must actually change something.

Counting the start gene as a mutation

✗ Wrong

q = deque([(startGene, 1)])

✓ Right

q = deque([(startGene, 0)])

The answer counts mutations, not genes visited — reaching the start requires zero. Unlike Word Ladder, which counts words in the sequence, this one starts at 0.

Not checking the bank membership of the target

✗ Wrong

q = deque([(startGene, 0)])

✓ Right

if endGene not in bankSet:
    return -1

Every intermediate gene must be in the bank, including the final one. Without the check the BFS exhausts the reachable set before concluding, and the intent is less obvious.

06

Edge cases

endGene not in bank

Return -1 without running BFS.

startGene equals endGene

Not a real test case per constraints, but would need 0 mutations.

bank has unrelated genes

Never generated as neighbors, simply ignored.

No mutation path exists

BFS exhausts the queue without reaching endGene; return -1.

07

Complexity

Time

O(n * L * 4)

Space

O(n * L)

n = bank size, L = gene length; same shape as Word Ladder with a 4-letter alphabet.