问题描述
思路
状态：dp[i]表示考虑0到i-1所表示的字符串可不可以被拆分成单词 状态转移方程在程序中有，不难理解
代码
class Solution {
public:
bool wordBreak(string s
, vector
<string
>& wordDict
) {
int n
=s
.size();
vector
<bool> dp(n
+1,false);
unordered_set
<string
> m(wordDict
.begin(),wordDict
.end());
dp
[0]=true;
for(int i
=1;i
<=n
;i
++) {
for(int j
=0;j
<i
;j
++) {
if(dp
[j
]==true&&m
.find(s
.substr(j
,i
-j
))!=m
.end()) {
dp
[i
]=true;
break;
}
}
}
return dp
[n
];
}
};
