最小基因变化
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
示例 1：
codeType
输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1
示例 2：
codeType
输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2
示例 3：
codeType
输入：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'] 组成
解法
ts
function minMutation(startGene: string, endGene: string, bank: string[]): number {
// 每次可以变化一位，但是变化的结果必须要在bank中
// 每次变化相当于一条路径，从基因A变成基因B
// 由此构建出图，从A变到目标C的路径次数就是变化次数
// 可以通过广度优先遍历得到最短路径
const m = startGene.length // 序列长度
const n = bank.length // 有多少种序列
// 先根据bank创建临接表
const adj = new Array(n).fill(0).map(() => new Array())
let endIndex = -1 // 结果在临接表中的索引
for(let i = 0; i < n; i++){
if(endGene === bank[i]){
endIndex = i
}
for(let j = i + 1; j < n; j++){ // 将当前基因和其它基因做比较
let diff = 0 // 基因的不同个数
for(let k = 0; k < m; k++){
if(bank[i][k] !== bank[j][k]){
diff++ // 基因不同个数++
}
if(diff > 1){ // 不同个数大于1就无法临接
break
}
}
if(diff === 1){ // 互为临接节点
adj[i].push(j)
adj[j].push(i)
}
}
}
if(endIndex === -1) return -1 // 基因库没有目标节点
// 广度优先遍历
const q = []
const visited = new Array(n).fill(false) // 记录访问过的节点，防止有环
let step = 1
for(let i = 0; i < n; i++){ // 先将一次变化就能抵达的基因入队
let diff = 0
for(let j = 0; j < m; j++){
if(startGene[j] !== bank[i][j]){
diff++ // 基因不同个数++
}
if(diff > 1){ // 不同个数大于1就无法临接
break
}
}
if(diff === 1){
q.push(i)
visited[i] = true // 访问过该节点
}
}
while(q.length !== 0){
const len = q.length
for(let i = 0; i < len; i++){ // 因为要记录step，所以得一层一层访问
const cur = q.shift()
if(cur === endIndex){ // 匹配到目标，直接结束
return step
}
// 将其领接节点入队（未访问过的）
for(const next of adj[cur]){
if(visited[next]) continue // 访问过了，跳过
visited[next] = true
q.push(next)
}
}
step++
}
return -1
};