Задача: 127. Word Ladder
Сложность: hard

Секвенция трансформации от слова beginWord к слову endWord с использованием словаря wordList представляет собой последовательность слов beginWord -> s1 -> s2 -> ... -> sk, при которой:

Каждая пара соседних слов отличается ровно одной буквой.
Каждый элемент si для 1 <= i <= k присутствует в wordList. Отметим, что beginWord не обязан быть в wordList.
sk равно endWord.
Для двух слов, beginWord и endWord, и словаря wordList, верните количество слов в кратчайшей секвенции трансформации от beginWord к endWord, или 0, если такая секвенция не существует.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

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

1⃣Препроцессинг списка слов: Осуществите препроцессинг заданного списка слов (wordList), чтобы найти все возможные промежуточные состояния слов. Сохраните эти состояния в словаре, где ключом будет промежуточное слово, а значением — список слов, имеющих то же промежуточное состояние.

2⃣Использование очереди для обхода: Поместите в очередь кортеж, содержащий beginWord и число 1, где 1 обозначает уровень узла. Вам нужно вернуть уровень узла endWord, так как он будет представлять длину кратчайшей последовательности преобразования. Используйте словарь посещений, чтобы избежать циклов.

3⃣Поиск кратчайшего пути через BFS (обход в ширину): Пока в очереди есть элементы, получите первый элемент очереди. Для каждого слова определите все промежуточные преобразования и проверьте, не являются ли эти преобразования также преобразованиями других слов из списка. Для каждого найденного слова, которое имеет общее промежуточное состояние с текущим словом, добавьте в очередь пару (слово, уровень + 1), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int LadderLength(string beginWord, string endWord, IList<string> wordList) {
        int L = beginWord.Length;
        Dictionary<string, List<string>> allComboDict = new Dictionary<string, List<string>>();
        foreach (string word in wordList) {
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                if (!allComboDict.ContainsKey(newWord))
                    allComboDict[newWord] = new List<string>();
                allComboDict[newWord].Add(word);
            }
        }

        Queue<Tuple<string, int>> Q = new Queue<Tuple<string, int>>();
        Q.Enqueue(new Tuple<string, int>(beginWord, 1));
        Dictionary<string, bool> visited = new Dictionary<string, bool>();
        visited[beginWord] = true;
        while (Q.Any()) {
            var node = Q.Dequeue();
            string word = node.Item1;
            int level = node.Item2;
            for (int i = 0; i < L; i++) {
                string newWord = word.Substring(0, i) + '*' + word.Substring(i + 1, L - i - 1);
                foreach (string adjacentWord in allComboDict.GetValueOrDefault(newWord, new List<string>())) {
                    if (adjacentWord.Equals(endWord))
                        return level + 1;
                    if (!visited.ContainsKey(adjacentWord)) {
                        visited[adjacentWord] = true;
                        Q.Enqueue(new Tuple<string, int>(adjacentWord, level + 1));
                    }
                }
            }
        }

        return 0;
    }
}

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