Задача: 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.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int MinMutation(string start, string end, string[] bank) {
        Queue<string> queue = new Queue<string>();
        HashSet<string> seen = new HashSet<string>();
        queue.Enqueue(start);
        seen.Add(start);
        
        int steps = 0;
        while (queue.Count > 0) {
            int nodesInQueue = queue.Count;
            
            for (int j = 0; j < nodesInQueue; j++) {
                string node = queue.Dequeue();
                
                if (node == end) {
                    return steps;
                }
                
                foreach (char c in "ACGT") {
                    for (int i = 0; i < node.Length; i++) {
                        char[] neighborArray = node.ToCharArray();
                        neighborArray[i] = c;
                        string neighbor = new string(neighborArray);
                        if (!seen.Contains(neighbor) && Array.Exists(bank, b => b == neighbor)) {
                            queue.Enqueue(neighbor);
                            seen.Add(neighbor);
                        }
                    }
                }
            }
            
            steps++;
        }
        
        return -1;
    }
}

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