[LeetCode] Word Ladder II

简介: This is a tough problem! I read some solutions from the web. This link provides a one-end BFS solution.

This is a tough problem! I read some solutions from the web. This link provides a one-end BFS solution. The code is reorganized as follows.

 1 class Solution {
 2 public:
 3     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
 4         dict.insert(end);
 5         unordered_set<string> current;
 6         unordered_set<string> 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<string, vector<string> > ancestors;
25     vector<string> ladder;
26     vector<vector<string> > ladders;
27     
28     void findChildren(string& word, unordered_set<string>& next, unordered_set<string>& 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 };

This link shares a two-end BFS solution, which is much faster! I have also rewritten that code below. 

 1 class Solution {
 2 public:
 3     vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
 4         vector<string> ladder;
 5         vector<vector<string> > ladders;
 6         ladder.push_back(start);
 7         unordered_set<string> startWords;
 8         unordered_set<string> endWords;
 9         startWords.insert(start);
10         endWords.insert(end);
11         unordered_map<string, vector<string> > 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<string>& startWords, unordered_set<string>& endWords,
19                        unordered_map<string, vector<string> >& children, unordered_set<string>& dict,
20                        vector<string>& ladder, vector<vector<string> >& 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<string> 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<string, vector<string> >& children,
51                     vector<string>& ladder, vector<vector<string> >& 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 };

 

目录
相关文章
LeetCode 318. Maximum Product of Word Lengths
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
77 0
LeetCode 318. Maximum Product of Word Lengths
LeetCode 290. Word Pattern
给定一种 pattern(模式) 和一个字符串 str ,判断 str 是否遵循相同的模式。 这里的遵循指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式。
49 0
LeetCode 290. Word Pattern
LeetCode 212. Word Search II
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
79 0
LeetCode 212. Word Search II
|
索引
LeetCode 79. Word Search
给定一个2D板和一个单词,找出该单词是否存在于网格中。 该单词可以由顺序相邻的单元的字母构成,其中“相邻”单元是水平或垂直相邻的单元。 相同的字母单元格不得多次使用。
76 0
LeetCode 79. Word Search
|
索引 存储
LeetCode 290 Word Pattern(单词模式)(istringstream、vector、map)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50611509 翻译 给定一个模式,和一个字符串str,返回str是否符合相同的模式。
957 0
LeetCode 58 Length of Last Word(最后单词的长度)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50592917 翻译 给定一个包含大小写字母和空格字符的字符串, 返回该字符串中最后一个单词的长度。
728 0