In this approach, we utilize the Breadth-First Search algorithm to explore the mutation process. The problem can be transformed into finding the shortest path in an unweighted graph (where nodes are gene strings and edges represent valid transformations as per the gene bank).

Steps involved:

Use a queue to perform the BFS starting from the startGene.
Use a set to store visited nodes to prevent re-processing.
The queue will store pairs representing the current gene string and the number of mutations so far.
Iteratively explore valid mutations (one letter changes) that are in the gene bank.
If the endGene is reached, return the mutation count.
If the queue is exhausted without finding the endGene, return -1.

Time Complexity: O(N * M * 4) where N is the number of steps in bank, M is length of startGene (8), and 4 is from trying each nucleotide.

Space Complexity: O(N) for the queue.

C C++Java Python C#JavaScript

1from collections import deque
2
3class Solution:
4    def minMutation(self, startGene: str, endGene: str, bank: [str]) -

Explanation

The Python solution uses deque for BFS, with a set for fast checks and reductions on the bank. The core idea is to iterate over each gene character, trying possible valid mutations.

Bidirectional BFS Approach

This approach aims to optimize the BFS by conducting simultaneous searches from both the start and end genes. This reduces the search space effectively.

Steps:

Initialize forward and backward sets with the startGene and endGene, respectively.
Use a set for the gene bank to ensure quick look-up and process unvisited genes.
Iteratively expand the forward and backward sets, swapping as necessary to always expand the smaller set.
If a common gene is found in both sets, return the combined step count.
If expansion is exhausted without finding an intersection, return -1.

Time Complexity: O(N * M * 4), with quicker terminations due to bidirectional checks.

Space Complexity: O(N) for two sets tracking forward and backward layers.

C++Python

1#include <iostream>
2#include <unordered_set>
3#include <vector>
using namespace std;

int minMutation(string startGene, string endGene, vector<string>& bank) {
    unordered_set<string> geneBank(begin(bank), end(bank));
    if (!geneBank.count(endGene)) return -1;

    unordered_set<string> forward = {startGene};
    unordered_set<string> backward = {endGene};

    int steps = 0;
    vector<char> choices = {'A', 'C', 'G', 'T'};

    while (!forward.empty() && !backward.empty()) {
        if (forward.size() > backward.size())
            swap(forward, backward);

        unordered_set<string> nextLevel;

        for (const string& gene : forward) {
            string currentGene = gene;
            
            for (int i = 0; i < currentGene.size(); ++i) {
                char original = currentGene[i];
                for (char c : choices) {
                    currentGene[i] = c;
                    if (backward.find(currentGene) != backward.end())
                        return steps + 1;

                    if (geneBank.find(currentGene) != geneBank.end()) {
                        nextLevel.insert(currentGene);
                        geneBank.erase(currentGene);
                    }
                }
                currentGene[i] = original;
            }
        }

        swap(forward, nextLevel);
        ++steps;
    }

    return -1;
}

int main() {
    vector<string> bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    cout << minMutation("AACCGGTT", "AAACGGTA", bank) << endl;
    return 0;
}

DSA Corner

Home

DSA Corner

DSA Corner

DSA Corner

DSA Corner

DSA Corner

DSA Corner

433. Minimum Genetic Mutation

Breadth-First Search (BFS) Approach

Explanation

Bidirectional BFS Approach

Similar Problems

Related Topics

Problem Stats

Practice on LeetCode

Explanation