[LeetCode] 433. Minimum Genetic Mutation

😎풀이

1. BFS를 활용하여 현재 문자의 일부를 변경하며 순회
   1-1. 현재 인덱스 문자를 A, C, G, T로 변경해가며, bank에 존재하는 문자인지 판별
   1-2. 최종적으로 endGene에 맞게 변형되는 최소 변형 결과 반환
2. 모든 경우의 수에서 변형이 불가하다면, -1 반환

function minMutation(startGene: string, endGene: string, bank: string[]): number {
    const bankSet = new Set(bank)
    if(startGene === endGene && bankSet.has(startGene)) return 0
    const queue: [string, number][] = [[startGene, 0]]
    const visited = new Set<string>([startGene])
    const choices = ['A', 'C', 'G', 'T']
    while(queue.length) {
        const [gene, mutation] = queue.shift()
        for(let i = 0; i < gene.length; i++) {
            for(const choice of choices) {
                const newGene = gene.slice(0, i) + choice + gene.slice(i + 1)
                const nextMutation = mutation + 1
                if(!bankSet.has(newGene)) continue
                if(visited.has(newGene)) continue
                if(newGene === endGene) return nextMutation
                visited.add(newGene)
                queue.push([newGene, nextMutation])
            }
        }
    }
    return -1
};