A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:
Every adjacent pair of words differs by a single letter.
Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].
class Solution {
public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end()), current, next;
if (dict.find(endWord) == dict.end()) {
return {};
}
unordered_map<string, vector<string>> children;
vector<vector<string>> ladders;
vector<string> ladder;
current.insert(beginWord);
ladder.push_back(beginWord);
while (true) {
for (string word : current) {
dict.erase(word);
}
for (string word : current) {
findChildren(word, next, dict, children);
}
if (next.empty()) {
break;
}
if (next.find(endWord) != next.end()) {
genLadders(beginWord, endWord, children, ladder, ladders);
break;
}
current.clear();
swap(current, next);
}
return ladders;
}
private:
void findChildren(string word, unordered_set<string>& next, unordered_set<string>& dict, unordered_map<string, vector<string>>& children) {
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;
}
}
void genLadders(string beginWord, string endWord, unordered_map<string, vector<string>>& children, vector<string>& ladder, vector<vector<string>>& ladders) {
if (beginWord == endWord) {
ladders.push_back(ladder);
} else {
for (string child : children[beginWord]) {
ladder.push_back(child);
genLadders(child, endWord, children, ladder, ladders);
ladder.pop_back();
}
}
}
};
