π Problem Details
- Title:
433. Minimum Genetic Mutation
- Link: https://leetcode.com/problems/minimum-genetic-mutation/
- Difficulty: Medium
- Tags/Categories: BFS Queue Hashmap Strings
πWhat Were My Initial Thoughts?
use of a hashmap to store char values and a vector of all index retaining to that mutation value
(not correct)
π€What Did I Struggle With?
Was unable to come up with the graph interpretation
Intuition for BFS:
1. Problem Representation:
- each gene (string) can be seen as a node
- a valid single-char mutation transforms one gene into another, forming an edge between two nodes
- the task is to find the shortest path from the
startGene
to theendGene
through this graph, where the valid genes are in the bank
2. Layered Exploration:
- BFS explores all nodes (mutations) at the same βdistanceβ (i.e. single mutation steps) before moving to nodes further away.
- This ensures that when you reach
endGene
, youβve found the shortest path possible
3. Efficiency / Optimization:
- BFS avoids revisiting already-explored genes (nodes), reducing redundant computation
- By storing valid genes in a set (or hashmap), we can quickly check if a gene is part of the bank
π‘ Explanation of Solution
BFS Approach:
1. init
- create a queue of pairs, starting with the startGene and an initial mutation count of 0
- create a set representation of genes in bank
- create a set for visited to avoid redundant computation
2. iterative exploration
- while the queue is not empty
- deque the current gene and its mutation count
- for each character position in the current gene
- replace the character with one of the three other possible characters [A, C, G, T]
- generate a new gene (potential neighbour)
- if the new gene matches endGene, return the mutation count + 1
- if the new gene exists in the bank and has been visited:
- mark it as visited
- enqueue the new gene with the updated mutation count
3. termination
- if the queue is empty and endGene hasn't been reached, return -1 (no valid mutation path exists)
β Complexity Analysis
Time Complexity: O(n)
- constant string length (8), which keeps the number of mutations per node bounded
- efficient O(1) lookups for validation using set
- n represents the number of elements in bank
Space Complexity: O(n)
- visited set stores up to n nodes
- queue stores nodes to be processed, worst case of n nodes in the queue
- bank set stores n elements
π» Implementation of Solution
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
// Convert the bank into an unordered_set for O(1) lookups
unordered_set<string> geneBank(bank.begin(), bank.end());
// If endGene is not in the bank, return -1 immediately
if (geneBank.find(endGene) == geneBank.end()) {
return -1;
}
// BFS setup
queue<pair<string, int>> q; // Pair of current gene and mutation count
q.push({startGene, 0});
unordered_set<string> visited; // To avoid revisiting genes
visited.insert(startGene);
// Possible mutations for each character
const char mutations[] = {'A', 'C', 'G', 'T'};
// BFS loop
while (!q.empty()) {
auto [currentGene, mutationsCount] = q.front();
q.pop();
// Try mutating each character of the current gene
for (int i = 0; i < currentGene.size(); ++i) {
char originalChar = currentGene[i];
for (char mutation : mutations) {
if (mutation == originalChar) continue;
// Generate a new gene by mutating one character
currentGene[i] = mutation;
// If the new gene matches the endGene, return the result
if (currentGene == endGene) {
return mutationsCount + 1;
}
// If the new gene is valid and not visited, enqueue it
if (geneBank.find(currentGene) != geneBank.end() && visited.find(currentGene) == visited.end()) {
visited.insert(currentGene);
q.push({currentGene, mutationsCount + 1});
}
}
// Revert the change to try other mutations
currentGene[i] = originalChar;
}
}
// If we exhaust all possibilities without finding the endGene
return -1;
}
};