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

Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:
Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

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

1️⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

2️⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList.

3️⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths.

😎 Решение:

var findLadders = function(beginWord, endWord, wordList) {
    let adjList = {};
    let currPath = [endWord];
    let shortestPaths = [];
    let wordSet = new Set(wordList);

    function findNeighbors(word) {
        let neighbors = [];
        let charList = Array.from(word);
        for (let i = 0; i < charList.length; i++) {
            let oldChar = charList[i];
            for (let c = 'a'.charCodeAt(0); c <= 'z'.charCodeAt(0); c++) {
                if (c !== oldChar.charCodeAt(0)) {
                    charList[i] = String.fromCharCode(c);
                    let newWord = charList.join("");
                    if (wordSet.has(newWord)) neighbors.push(newWord);
                }
            }
            charList[i] = oldChar;
        }
        return neighbors;
    }

    function backtrack(source) {
        if (source === endWord) {
            shortestPaths.push([...currPath].reverse());
            return;
        }
        adjList[source]?.forEach(neighbor => {
            currPath.push(neighbor);
            backtrack(neighbor);
            currPath.pop();
        });
    }

    function bfs() {
        let queue = [beginWord];
        wordSet.delete(beginWord);
        while (queue.length) {
            let current = queue.shift();
            let neighbors = findNeighbors(current);
            neighbors.forEach(neighbor => {
                if (!adjList[neighbor]) adjList[neighbor] = [];
                adjList[neighbor].push(current);
                if (!wordSet.has(neighbor)) {
                    queue.push(neighbor);
                    wordSet.delete(neighbor);
                }
            });
        }
    }

    bfs();
    backtrack(beginWord);
    return shortestPaths;
};

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