Google+ Followers

Wednesday, November 20, 2013

[LeetCode] WordBreak II, Solution

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

[Thoughts]

既然是要给出所有解,那就递归好了,但是递归的过程中注意剪枝。

 

[Code]

没有剪枝版

1 vector<string> wordBreak(string s, unordered_set<string> &dict) {
2 string result;
3 vector<string> solutions;
4 int len = s.size();
5 GetAllSolution(0, s, dict, len, result, solutions);
6 return solutions;
7 }
8
9 void GetAllSolution(int start, const string& s, const unordered_set<string> &dict, int len, string& result, vector<string>& solutions)
10 {
11 if (start == len)
12 {
13 solutions.push_back(result.substr(0, result.size()-1));//eliminate the last space
14 return;
15 }
16 for (int i = start; i< len; ++i)
17 {
18 string piece = s.substr(start, i - start + 1);
19 if (dict.find(piece) != dict.end() && possible[i+1])
20 {
21 result.append(piece).append(" ");
22 GetAllSolution(i + 1, s, dict, len, result, solutions);
23 result.resize(result.size() - piece.size()-1);
24 }
25 }
26 }

但是很明显,这种裸的递归,效率太低,因为有大量的重复计算,肯定过不了测试数据。

剪枝版

这里加上一个possible数组,如同WordBreak I里面的DP数组一样,用于记录区间拆分的可能性


Possible[i] = true 意味着 [i,n]这个区间上有解


加上剪枝以后,运行时间就大大减少了。(Line 5, 20, 23, 25,26为剪枝部分)


1 vector<string> wordBreak(string s, unordered_set<string> &dict) {
2 string result;
3 vector<string> solutions;
4 int len = s.size();
5 vector<bool> possible(len+1, true); // to record the search which has been executed once
6 GetAllSolution(0, s, dict, len, result, solutions, possible);
7 return solutions;
8 }
9
10 void GetAllSolution(int start, const string& s, const unordered_set<string> &dict, int len, string& result, vector<string>& solutions, vector<bool>& possible)
11 {
12 if (start == len)
13 {
14 solutions.push_back(result.substr(0, result.size()-1));//eliminate the last space
15 return;
16 }
17 for (int i = start; i< len; ++i)
18 {
19 string piece = s.substr(start, i - start + 1);
20 if (dict.find(piece) != dict.end() && possible[i+1]) // eliminate unnecessory search
21 {
22 result.append(piece).append(" ");
23 int beforeChange = solutions.size();
24 GetAllSolution(i + 1, s, dict, len, result, solutions, possible);
25 if(solutions.size() == beforeChange) // if no solution, set the possible to false
26 possible[i+1] = false;
27 result.resize(result.size() - piece.size()-1);
28 }
29 }
30 }

suoyi

Post a Comment