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

😎 Решение:

function ladderLength($beginWord, $endWord, $wordList) {
    $L = strlen($beginWord);
    $allComboDict = [];
    foreach ($wordList as $word) {
        for ($i = 0; $i < $L; $i++) {
            $newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
            if (!isset($allComboDict[$newWord])) {
                $allComboDict[$newWord] = [];
            }
            $allComboDict[$newWord][] = $word;
        }
    }

    $queue = [[$beginWord, 1]];
    $visited = [$beginWord => true];
    while (count($queue) > 0) {
        $node = array_shift($queue);
        $word = $node[0];
        $level = $node[1];
        for ($i = 0; $i < $L; $i++) {
            $newWord = substr($word, 0, $i) . '*' . substr($word, $i + 1);
            if (!isset($allComboDict[$newWord])) {
                $allComboDict[$newWord] = [];
            }
            foreach ($allComboDict[$newWord] as $adjacentWord) {
                if ($adjacentWord === $endWord) {
                    return $level + 1;
                }
                if (!isset($visited[$adjacentWord])) {
                    $visited[$adjacentWord] = true;
                    $queue[] = [$adjacentWord, $level + 1];
                }
            }
        }
    }

    return 0;
}

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