[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