Interview Classic 150 Questions P443 Minimum Genetic Change

---

Timeline

Timeline

2025-11-23

init

---

Problem:

P443 Minimum Genetic Change

https://leetcode.cn/problems/minimum-genetic-mutation/?envType=study-plan-v2&envId=top-interview-150

Since using string as a key for hashing requires strcmp, the performance is not high. Use int as a hexadecimal number, which is exactly 8 digits in total.

#include <cassert>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using std::vector;
using std::string;
using std::unordered_map;
using std::unordered_set;
using std::queue;

#define GENE_LENGTH 8

class Solution {
    private:
	int gene_str2int(string gene)
	{
		int val = 0;
		int i, n = gene.size();
		assert(n < 10);
		unordered_map<char, int> ch2int = { { 'A', 0x0 }, { 'C', 0x1 }, { 'T', 0x2 }, { 'G', 0x3 } };
		for (i = 0; i < n; i++) {
			val |= ch2int[gene[i]] << i * 4;
		}
		return val;
	}
	vector<int> get_possible_neighbors(int gene_id)
	{
		vector<int> vec;
		int curr, next, neighbor;
		for (int i = 0; i < GENE_LENGTH; i++) {
			curr = (gene_id >> (4 * i)) & 0xF;
			for (int j = 1; j <= 3; j++) {
				next = (curr + j) % 4;
				neighbor = (gene_id & ~(0xF << (4 * i))) | (next << (4 * i));
				vec.push_back(neighbor);
			}
		}
		return vec;
	}

    public:
	int minMutation(string startGene, string endGene, vector<string> &bank)
	{
		unordered_set<int> bank_set;
		unordered_set<int> visited;
		vector<int> neighbors;
		queue<int> q;
		int i, gene_id, level = 0;
		int target_gene_id = gene_str2int(endGene);

		for (string &gene : bank) {
			bank_set.insert(gene_str2int(gene));
		}

		q.push(gene_str2int(startGene));

		while (!q.empty()) {
			int q_size = q.size();
			for (i = 0; i < q_size; i++) {
				gene_id = q.front();
				visited.insert(gene_id);
				q.pop();
				if (gene_id == target_gene_id) {
					return level;
				}
				neighbors = get_possible_neighbors(gene_id);
				for (int &neighbor : neighbors) {
					if (bank_set.count(neighbor) && !visited.count(neighbor)) {
						q.push(neighbor);
					}
				}
			}

			level++;
		}
		return -1;
	}
};