Minimum Genetic Mutation

Find the shortest path between gene strings using BFS on a valid mutation graph.

bfs graph string queue

A gene string is a string of length 8 composed of the characters 'A', 'C', 'G', and 'T'. A single mutation changes exactly one character of the gene string to another of these four characters. A mutation is valid only if the resulting gene string is present in the provided bank (list of valid gene strings).

Given a start gene string `startGene`, an end gene string `endGene`, and a list of valid gene strings `bank`, write a function:

```python
def min_mutation(startGene: str, endGene: str, bank: list[str]) -> int:
```

that returns the **minimum number of mutations** needed to transform `startGene` into `endGene`. If it is impossible, return `-1`.

Notes:
- The start gene is always assumed to be valid, so you may mutate to it even if it is not in the bank (but you do not need to return to it).
- If `endGene` is not in the bank, return `-1` (unless it equals `startGene`, in which case return 0).
- The same gene string may appear multiple times in the bank (ignore duplicates).
- You may not use a gene string that is not in the bank as an intermediate step, except for the starting string which is already given.
- The bank list is non-empty (length >= 1), but it may not contain the end gene.

Return the minimum number of mutations (integer).

Constraints

• `startGene.length == 8`
• `endGene.length == 8`
• `bank.length >= 1`
• Each string in bank has length 8 and contains only characters from {'A','C','G','T'}.
• `startGene` and `endGene` also consist only of those characters.
• Time complexity: O((bank.length)^2 * 8) or O(bank.length * 4 * 8) is acceptable.
• Space complexity: O(bank.length).

Example

>>> min_mutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"])
1
>>> min_mutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"])
2
>>> min_mutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"])
3
>>> min_mutation("AACCGGTT", "AACCGGTA", [])
-1

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Model this as an unweighted graph where each valid gene string is a node, and an edge exists between two nodes if they differ by exactly one character.

Use breadth-first search (BFS) from startGene to find the shortest path to endGene. If you never reach endGene, return -1.

Remember that startGene may not be in the bank, so treat it as the initial node even if it's not in the bank list.

If startGene equals endGene, return 0 immediately.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.