Пример словарной лестницы
Для двух слов (beginWord и endWord) и списка слов словаря найдите все кратчайшие последовательности преобразований от beginWord до endWord, такое, что:
- Одновременно можно изменить только одну букву
- Каждое преобразованное слово должно существовать в списке слов. Обратите внимание, что 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; } };
Ресурсы