题解 | #训练聪明的牛#
训练聪明的牛
https://www.nowcoder.com/practice/971090dbcf5043e295b4ea7f6ec85311
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param wordDict string字符串vector
* @return bool布尔型
*/
bool wordBreak(string s, vector<string>& wordDict) {
// write code here
// 用一个数组dp[i] 表示前i个字符可以用wordDict表示
int len = s.size();
vector<int> dp(len+1);
dp[0] = 1;
unordered_set<string> wordDictset(wordDict.begin(), wordDict.end());
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictset.count(s.substr(j, i-j))) {
dp[i] = 1;
break;
}
}
}
return dp[len] == 1;
}
};
