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.

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

python

▶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

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.

06

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.