Пример словарной лестницы

Для двух слов (beginWord и endWord) и списка слов словаря найдите все кратчайшие последовательности преобразований от beginWord до endWord, такое, что:

  1. Одновременно можно изменить только одну букву
  2. Каждое преобразованное слово должно существовать в списке слов. Обратите внимание, что beginWord не преобразованное слово.

Примечание.

  • Вернуть пустой список, если такой последовательности преобразования нет.
  • Все слова имеют одинаковую длину.
  • Все слова содержат только буквы нижнего регистра.
  • Вы можете предположить, что в списке слов нет дубликатов.
  • Вы можете предположить, что beginWord и endWord непустые и не одно и то же.

Пример 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Пример 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Решение

Идея состоит в том, чтобы сначала использовать BFS для поиска от beginWord до endWord и одновременно сгенерировать сопоставление слов с дочерними элементами. Затем используйте DFS (отслеживание с возвратом), чтобы сгенерировать последовательности преобразования в соответствии с отображением.

class Solution {
    
    // Finds endWord by BFS and create parent->children word relations
    bool findEndWordByBFS(const string& beginWord, 
                          const string& endWord,
                          const vector<string>& wordList,
                          unordered_map<string, vector<string>>& children) {
        unordered_set<string> dict(wordList.begin(), wordList.end()), current, next;
        current.insert(beginWord);
        while (true) {
            for (string word : current) {
                dict.erase(word);
            }
            
            for (string word : current) {
                string parent = word;
                for (int i = 0; i < word.size(); i++) {
                    char t = word[i];
                    for (int j = 0; j < 26; j++) {
                        word[i] = 'a' + j;
                        if (dict.find(word) != dict.end()) {
                            next.insert(word);
                            children[parent].push_back(word);
                        }
                    }
                    word[i] = t;
                }
}
            
            if (next.empty())
                return false;
            
            if (next.find(endWord) != next.end())
                return true;
current.clear();
            swap(current, next);
        } 
        
        return false;
    }
    //  Use DFS (backtracking) to generate the transformation sequences according to the mapping
    void buildLadders(const string& beginWord,
                      const string& endWord,
                      vector<string>& ladder,
                      vector<vector<string>>& ladders,
                      unordered_map<string, vector<string>>& children) {
        if (beginWord == endWord) {
            ladders.push_back(ladder);
        } else {
            for (string word : children[beginWord]) {
                ladder.push_back(word);
                buildLadders(word, endWord, ladder, ladders, children);
                ladder.pop_back();
            }
        }
    }
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end())
            return {};
        unordered_map<string, vector<string>> children;
        if (!findEndWordByBFS(beginWord, endWord, wordList, children))
            return {};
        vector<vector<string>> ladders;
        vector<string> ladder;
        ladder.push_back(beginWord);
        buildLadders(beginWord, endWord, ladder, ladders, children);
        return ladders;
    }
};

Ресурсы