题解 | #基因变异最小次数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param start string字符串 
 * @param end string字符串 
 * @param bank string字符串一维数组 
 * @return int整型
 */
function minMutation(start, end, bank) {
    // write code here
    if (!bank.includes(end)) {
        return -1
    }

    let chars = ['A', 'C', 'G', 'T']

    let queue = [[start, 0]]
    let bankSet = new Set(bank)
    let visitedSet = new Set([start])

    while (queue.length > 0) {
        let [current, step] = queue.shift()

        if (current === end) {
            return step
        }

        for (let i = 0; i < current.length; i++) {
            for (let j = 0; j < chars.length; j++) {
                let newWord = current.slice(0, i) + chars[j] + current.slice(i + 1)

                if (bankSet.has(newWord) && !visitedSet.has(newWord)) {
                    queue.push([newWord, step + 1])
                    visitedSet.add(newWord)
                }
            }
        }

    }

    return -1
}
module.exports = {
    minMutation: minMutation
};