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

Дано: beginWord, endWord и wordList. Найдите длину кратчайшей цепочки преобразования из beginWord в endWord, где каждое слово отличается ровно одной буквой, и каждое промежуточное слово должно быть в wordList.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" → "hot" → "dot" → "dog" → "cog" — цепочка из 5 слов

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

1⃣Преобразование слов:
Для каждого слова из wordList формируем промежуточные состояния, заменяя по одной букве на *.
Например, "hot" → "*ot", "h*t", "ho*".
Сохраняем в unordered_map<string, vector<string>> allComboDict.

2⃣BFS:
Стартуем с beginWord, кладем в очередь (beginWord, 1) — слово и уровень.
Храним visited, чтобы не зациклиться.
На каждом шаге:
генерируем все промежуточные состояния *ot, h*t, ...
смотрим в allComboDict, какие слова подходят
добавляем их в очередь с level + 1
если встречаем endWord — возвращаем level + 1

3⃣Если очередь опустела, а endWord не найден — возвращаем 0.

😎 Решение:

#include <unordered_map>
#include <vector>
#include <queue>
#include <string>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int L = beginWord.size();
        unordered_map<string, vector<string>> allComboDict;

        for (string word : wordList) {
            for (int i = 0; i < L; i++) {
                string newWord = word.substr(0, i) + '*' + word.substr(i + 1);
                allComboDict[newWord].push_back(word);
            }
        }

        queue<pair<string, int>> Q;
        Q.push({beginWord, 1});
        unordered_map<string, bool> visited;
        visited[beginWord] = true;

        while (!Q.empty()) {
            auto [word, level] = Q.front();
            Q.pop();

            for (int i = 0; i < L; i++) {
                string newWord = word.substr(0, i) + '*' + word.substr(i + 1);

                for (string& adjacentWord : allComboDict[newWord]) {
                    if (adjacentWord == endWord) return level + 1;
                    if (!visited[adjacentWord]) {
                        visited[adjacentWord] = true;
                        Q.push({adjacentWord, level + 1});
                    }
                }
            }
        }

        return 0;
    }
};

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