Задача: 433. Minimum Genetic Mutation
Сложность: medium

Генетическая строка может быть представлена строкой длиной 8 символов, содержащей символы 'A', 'C', 'G' и 'T'.
Предположим, нам нужно исследовать мутацию от генетической строки startGene до генетической строки endGene, где одна мутация определяется как изменение одного символа в генетической строке.
Например, "AACCGGTT" --> "AACCGGTA" является одной мутацией.
Также существует генетический банк bank, который содержит все допустимые генетические мутации. Генетическая строка должна быть в банке, чтобы считаться допустимой.
Даны две генетические строки startGene и endGene и генетический банк bank, верните минимальное количество мутаций, необходимых для мутации от startGene до endGene. Если такой мутации не существует, верните -1.

Обратите внимание, что начальная строка считается допустимой, поэтому она может не быть включена в банк.

Пример:

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

👨‍💻 Алгоритм:

1⃣Инициализируйте очередь и множество seen. Очередь будет использоваться для выполнения BFS, а множество seen будет использоваться для предотвращения повторного посещения одного и того же узла. Изначально в очередь и множество должен быть помещен startGene.

2⃣Выполняйте BFS. На каждом узле, если node == endGene, верните количество шагов, пройденных до этого момента. В противном случае, итеративно заменяйте каждый символ в строке на один из "A", "C", "G", "T" для нахождения соседей. Для каждого соседа, если он еще не был посещен и находится в bank, добавьте его в очередь и в множество seen.

3⃣Если BFS завершился и endGene не был найден, задача невыполнима. Верните -1.

😎 Решение:

function minMutation(start, end, bank) {
    let queue = [start];
    let seen = new Set([start]);
    let steps = 0;

    while (queue.length > 0) {
        let nodesInQueue = queue.length;

        for (let j = 0; j < nodesInQueue; j++) {
            let node = queue.shift();

            if (node === end) {
                return steps;
            }

            for (let c of "ACGT") {
                for (let i = 0; i < node.length; i++) {
                    let neighbor = node.slice(0, i) + c + node.slice(i + 1);
                    if (!seen.has(neighbor) && bank.includes(neighbor)) {
                        queue.push(neighbor);
                        seen.add(neighbor);
                    }
                }
            }
        }

        steps++;
    }

    return -1;
}

console.log(minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"])); // Output: 1
console.log(minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"])); // Output: 2
console.log(minMutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"])); // Output: 3

Ставь 👍 и забирай 📚 Базу знаний