Minimum Genetic Mutation
Return the minimum number of mutations from start to end using bank entries.
Examples
Input: ["AACCGGTT","AACCGGTA",["AACCGGTA"]]
Output: 1
Input: ["AACCGGTT","AAACGGTA",["AACCGGTA","AACCGCTA","AAACGGTA"]]
Output: 2
Hints
Model the problem as a graph where each gene string is a node, and edges connect nodes that differ by exactly one character. The goal is to find the shortest path from start to end using BFS, ensuring the path only includes valid mutations present in the bank.
To handle invalid paths, pre-filter the bank to include only mutations that are one character away from the start gene. During BFS, skip any neighbor not in the filtered bank or already visited to avoid cycles and ensure correctness.
Optimize by using a queue for BFS and a visited set to track explored nodes. For each level of the BFS (representing one mutation), increment the mutation count. If the end gene is reached during the current level, return the count; otherwise, continue until the queue is exhausted.
Related Problems
Minimum Genetic Mutation
Return the minimum number of mutations from start to end using bank entries.