Minimum Genetic Mutation

Given a start gene string, an end gene string, and a bank of valid genes, return the minimum number of mutations needed to reach the end gene. Each mutation changes exactly one character. Pattern focus: Visited set. Use BFS with a visited set over gene states to avoid repeating the same string.

Input Format

startGene, endGene, bank = gene strings

Output Format

minimum number of mutations or -1

Constraints

  • 1 <= bank.length <= 10^5
  • All genes have length 8 and consist of A/C/G/T.

Examples

Example 1:

Input:

startGene = "AACCGGTT"
endGene = "AACCGGTA"
bank = ["AACCGGTA"]

Output:

1

Explanation:

One mutation changes the last character.

Example 2:

Input:

startGene = "AACCGGTT"
endGene = "AAACGGTA"
bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Output:

2

Explanation:

AACCGGTT -> AACCGGTA -> AAACGGTA.

Example 3:

Input:

startGene = "AAAAACCC"
endGene = "AACCCCCC"
bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]

Output:

3

Explanation:

A shortest valid path exists in 3 mutations.

Loading...
Minimum Genetic Mutation - Graph Traversal