leetcode 433 最小基因变化
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 ‘A’、’C’、’G’ 和 ‘T’ 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如，”AACCGGTT” –> “AACCGGTA” 就是一次基因变化。 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
示例1
输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1
示例2
输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2
示例3
输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3
提示：
- start.length == 8
- end.length == 8
- 0 <= bank.length <= 10
- bank[i].length == 8
- start、end 和 bank[i] 仅由字符 [‘A’, ‘C’, ‘G’, ‘T’] 组成
思路
拆解步骤：
- 如果 start 与 end 相等，此时直接返回0；如果最终的基因序列不在 bank 中，那么无法生成，则返回 -1
- 将可能变化的基因 s 从队列中取出，尝试所有可能变化后的基因，变化一次最多会生成 3 * 8 = 24 中不同的基因序列
- 检测当前生成的基因序列的合法性 si，首先使用哈希表测 si 是否存在数组 bank 中，如果则认为基因合法，否则该变化非法即丢弃；其次需要哈希表记录已经遍历过的基因序列，则将其加入到队列中
- 如果变化后的基因序列与 end 相等，则此时我们直接返回最小的变化次数即可；如果队列中所有的元素都已经遍历完成还无法完成 end，则此时无法实现目标变化，返回 -1。
代码
var characterReplacement = function(s, k) {
let left = 0;
let res = 0;
let counter = 0;
let frequence = new Array(26).fill(0);
for (let right = 0; right < s.length; right++) {
const distance = s[right].charCodeAt() - 'A'.charCodeAt();
frequence[distance] += 1;
counter = Math.max(counter, frequence[distance]);
while (right - left + 1 - counter > k) {
frequence[s[left].charCodeAt() - 'A'.charCodeAt()] -= 1;
left++;
}
res = Math.max(res, right - left + 1);
}
return res;
};
复杂度分析:
- 时间复杂度: O(CNM)
- 空间复杂度：O(N*M)