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"
.
本题如果暴力的话,超时
本题用动规
设dp[i]表示s[0,i)之间存在划分使分隔后的字符串都在dict里面
则
dp[i]=
true, 如果s[0,i)在dict里面
true,如果dp[k]=true (即s[0,k)存在划分在dict里面)且s[k,i)在dict里面
false,其他(默认)
注意程序是前闭后开
bool wordBreak(string s, unordered_set<string> &dict){
int n = s.length();
vector<bool> dp(n+,false);
dp[]=true;
for(int i = ; i < n+; ++ i){
for(int j = ; j < i; ++ j){
if(dp[j]&&dict.find(s.substr(j,i-j))!=dict.end()){
dp[i] = true;
break;
}
}
}
return dp[n];
}