[LeetCode] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

方法一：

DFS，

start已知，当start超过str长度时，说明全部字符串都能找到了。。

小数据可过，大数据时超时

Submission Result: Time Limit Exceeded

Last executed input:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

 1 class Solution {
 2     public:
 3         bool wordBreak(string s, unordered_set<string> &dict)
 4         {
 5             return wordBreak(s,0, dict);
 6         }   
 7 
 8         bool wordBreak(string s, int start, unordered_set<string> & dict)
 9         {   
10             size_t size =  s.size();
11             if(size == 0) return false;
12             if(start >= size)
13                 return true;
14 
15             for( int i = start; i <size; i++)
16             {   
17                 string str = s.substr(start, i-start+1);
18                 if(dict.find(str) != dict.end())
19                 {   
20                     if(wordBreak(s,i+1, dict))
21                        return true;
22                 }   
23 
24             }
25             return false;
26         }
27 };

方法二：

设状态为 f(i)，表示 s[0,i] 是否可以分词，则状态转移方程为
f(i) = any_of(f(j)&&s[j + 1, i] 2 dict), 0 j < i

 1 bool wordBreak2(string s, set<string> &dict) {
 2     vector<bool> f(s.size() + 1, false);
 3     f[0] = true; 
 4     for (int i = 1; i <= s.size(); ++i) {
 5         for (int j = i - 1; j >= 0; --j) {
 6             if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
 7                 f[i] = true;
 8                 break;
 9             }   
10         }   
11     }   
12     return f[s.size()];
13 }