Problem Statement

You have a gene sequence represented by an 8-character string, containing only 'A', 'C', 'G', or 'T' characters. To change from one gene sequence to another, you can mutate one character at a time.

For example, "AAAAACCC" --> "AAAACCCC" is one mutation.

Each intermediate sequence must be a valid gene in the provided list (bank).

The gene bank bank records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

Note: The starting point is assumed to be valid, so it might not be included in the bank.

Examples

Example 1:

• Input: startGene: "AACCGGTT", endGene: "AAACGGTA", bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
• Expected Output: 2
• Justification:
  • Mutations: "AACCGGTT" → "AACCGGTA" → "AAACGGTA"

Example 2:

• Input: startGene: "AAAAACCC", endGene: "AACCCCCC", bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
• Expected Output: 3
• Justification:
  • Mutations: "AAAAACCC" → "AAAACCCC" → "AAACCCCC" → "AACCCCCC"

Example 3:

• Input: startGene: "AACCGGTT", endGene: "CCGGTTAA", bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA", "CCGGTTAA"]
• Expected Output: -1
• Justification: We need to mutate a total of 8 characters, but the 'bank' array contains only 4 strings. So, it is not possible to perform 8 mutations.

Try it yourself

Try solving this question here: