433. 最小基因变化

🟠   🔖  广度优先搜索 哈希表 字符串  🔗 力扣 LeetCode

题目

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

• For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank bank that 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 bank, return the minimum number of mutations needed to mutate fromstartGenetoendGene. If there is no such a mutation, return -1.

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

Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]

Output: 1

Example 2:

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Output: 2

Constraints:

• 0 <= bank.length <= 10
• startGene.length == endGene.length == bank[i].length == 8
• startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T'].

题目大意

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。

另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

解题思路

这个问题可以视作是一个无权图的最短路径问题，每个基因序列是图中的节点，相邻节点是那些只相差一个字符的序列。要找最短路径，可以使用 广度优先搜索（BFS）。

1. 将起始序列放入队列，同时设定一个集合用于记录已经访问过的基因序列，避免重复访问。
2. 每次从队列中取出一个基因序列，尝试将其每个字符替换为 A、C、G、T，看看是否能得到一个新的有效序列（这个新序列需要在基因库中存在，且没有被访问过）。
3. 如果某次得到的序列等于目标序列，直接返回当前的变化次数。
4. 如果该序列有效且未访问，则将其加入队列，继续下一步的遍历。
5. 如果队列为空但还未找到目标序列，返回 -1，表示无法到达目标序列。

复杂度分析

• 时间复杂度：O(M * N)，其中 M 是基因序列的长度（8），N 是基因库的大小。对于每个序列，都有 8 个位置可以变化，每个位置可以选择 3 种不同的字符，因此时间复杂度相对较低。
• 空间复杂度：O(N)。

代码

/**
 * @param {string} startGene
 * @param {string} endGene
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function (startGene, endGene, bank) {
	let bankSet = new Set(bank); // 将bank转为set，查找更快
	if (!bankSet.has(endGene)) return -1;
	// 所有可能的字符
	const gene = ['A', 'G', 'C', 'T'];

	// BFS
	let queue = [startGene],
		visited = new Set([startGene]), // 记录已访问的基因序列
		step = 0;

	while (queue.length) {
		const len = queue.length;

		for (let i = 0; i < len; i++) {
			const cur = queue.shift();
			// 如果新的基因序列就是目标序列
			if (cur == endGene) {
				return step;
			}
			// 生成新的基因序列
			for (let newGene of getAllMutation(cur)) {
				// 如果新的基因序列在基因库中，且没有访问过
				if (!visited.has(newGene) && bankSet.has(newGene)) {
					queue.push(newGene);
					visited.add(newGene);
				}
			}
		}
		step++;
	}
	return -1;
};

// 求出所有可能的基因突变结果
var getAllMutation = function (gene) {
	let res = [],
		chars = gene.split('');

	for (let i = 0; i < chars.length; i++) {
		const char = chars[i];
		for (let newChar of ['A', 'G', 'C', 'T']) {
			chars[i] = newChar;
			res.push(chars.join(''));
		}
		chars[i] = char;
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
127	单词接龙	[✓]	广度优先搜索 哈希表 字符串