This is a tough problem! I read some solutions from the web. provides a one-end BFS solution. The code is reorganized as follows.
1 class Solution { 2 public: 3 vector > findLadders(string start, string end, unordered_set &dict) { 4 dict.insert(end); 5 unordered_set current; 6 unordered_set next; 7 current.insert(start); 8 ladder.push_back(end); 9 while (true) {10 for (string cur : current)11 dict.erase(cur);12 for (string cur : current)13 findChildren(cur, next, dict);14 if (next.empty()) return ladders;15 if (next.find(end) != next.end()) {16 genLadders(start, end);17 return ladders;18 }19 current.clear();20 swap(current, next);21 }22 }23 private:24 unordered_map > ancestors;25 vector ladder;26 vector > ladders;27 28 void findChildren(string& word, unordered_set & next, unordered_set & dict) {29 int len = word.length();30 string ancestor = word;31 for (int p = 0; p < len; p++) {32 char letter = word[p];33 for (int i = 0; i < 26; i++) {34 word[p] = 'a' + i;35 if (dict.find(word) != dict.end()) {36 next.insert(word);37 ancestors[word].push_back(ancestor);38 }39 }40 word[p] = letter;41 }42 }43 44 void genLadders(string& start, string& end) {45 if (start == end) {46 reverse(ladder.begin(), ladder.end());47 ladders.push_back(ladder);48 reverse(ladder.begin(), ladder.end());49 return;50 }51 for (string ancestor : ancestors[end]) {52 ladder.push_back(ancestor);53 genLadders(start, ancestor);54 ladder.pop_back();55 }56 }57 }; shares a two-end BFS solution, which is much faster! I have also rewritten that code below.
1 class Solution { 2 public: 3 vector > findLadders(string start, string end, unordered_set &dict) { 4 vector ladder; 5 vector > ladders; 6 ladder.push_back(start); 7 unordered_set startWords; 8 unordered_set endWords; 9 startWords.insert(start);10 endWords.insert(end);11 unordered_map > children;12 bool flip = true;13 if (searchLadders(startWords, endWords, children, dict, ladder, ladders, flip))14 genLadders(start, end, children, ladder, ladders);15 return ladders;16 }17 private:18 bool searchLadders(unordered_set & startWords, unordered_set & endWords,19 unordered_map >& children, unordered_set & dict,20 vector & ladder, vector >& ladders, bool& flip) {21 flip = !flip;22 if (startWords.empty()) return false;23 if (startWords.size() > endWords.size())24 return searchLadders(endWords, startWords, children, dict, ladder, ladders, flip);25 for (string word : startWords) dict.erase(word);26 for (string word : endWords) dict.erase(word);27 unordered_set intermediate;28 bool done = false;29 for (string word : startWords) {30 string temp = word;31 int len = word.length();32 for (int p = 0; p < len; p++) {33 char letter = word[p];34 for (int i = 0; i < 26; i++) {35 word[p] = 'a' + i;36 if (endWords.find(word) != endWords.end()) {37 done = true;38 flip ? children[word].push_back(temp) : children[temp].push_back(word);39 }40 else if (!done && dict.find(word) != dict.end()) {41 intermediate.insert(word);42 flip ? children[word].push_back(temp) : children[temp].push_back(word);43 }44 }45 word[p] = letter;46 }47 }48 return done || searchLadders(endWords, intermediate, children, dict, ladder, ladders, flip);49 }50 void genLadders(string& start, string& end, unordered_map >& children,51 vector & ladder, vector >& ladders) {52 if (start == end) {53 ladders.push_back(ladder);54 return;55 }56 for (string child : children[start]) {57 ladder.push_back(child);58 genLadders(child, end, children, ladder, ladders);59 ladder.pop_back();60 }61 }62 };