Задача: 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), где уровень — это уровень текущего слова. Если вы достигли искомого слова, его уровень покажет длину кратчайшей последовательности преобразования.

😎 Решение:

var ladderLength = function (beginWord, endWord, wordList) {
    let L = beginWord.length;
    let allComboDict = {};
    for (let word of wordList) {
        for (let i = 0; i < L; i++) {
            let newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);
            if (!allComboDict[newWord]) allComboDict[newWord] = [];
            allComboDict[newWord].push(word);
        }
    }
    let Q = [[beginWord, 1]];
    let visited = { [beginWord]: true };
    while (Q.length > 0) {
        let node = Q.shift();
        let word = node[0];
        let level = node[1];
        for (let i = 0; i < L; i++) {
            let newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);
            for (let adjacentWord of allComboDict[newWord] || []) {
                if (adjacentWord === endWord) {
                    return level + 1;
                }
                if (!visited[adjacentWord]) {
                    visited[adjacentWord] = true;
                    Q.push([adjacentWord, level + 1]);
                }
            }
        }
    }
    return 0;
};

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