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".
粗暴递归，结果超时
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 |
public class Solution { public
boolean wordBreak(String s, Set<String> dict) { if(s == null) return
false; int
start, end; start = end = 0; int
length = s.length(); while(start < length){ if( dict.contains(s.substring(0,start)) && wordBreak(s.substring(start+1),dict) ){ return
true; }else{ start++; } } return
false; }} |
| Last executed input: | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"] |
DP Solution:
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<bool> checked(s.length()+1, false); checked[0] = true; for (int i = 1; i <= s.length(); ++i) { for (int j = 0; j < i; ++j) { if (checked[j] && dict.find(s.substr(j,i-j)) != dict.end()) { checked[i] = true; break; } } } return checked[s.length()]; } };
LeetCode: Word Break,布布扣,bubuko.com
原文：http://www.cnblogs.com/yeek/p/3575184.html