艾恩凝
个人博客 https://aeneag.xyz/
cdsn好几年没更,记录刷题记录
题目链接
https://leetcode-cn.com/problems/word-break/
题解
这道题用动态规划解决,简单来说就是dp[i]为真时代表了前面i个子串是单词
// author : 艾恩凝
// blog : https://aeneag.xyz
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int len = s.size();
auto wordDictSet = unordered_set <string>();//新建一个无序集合
for(auto word : wordDict)wordDictSet.insert(word);//子单词插入到这个无序集合中
auto dp = vector<bool> (len+1);//动态规划dp数组
dp[0] = true;//第一项说明空串是true
for(int i = 1 ; i <= len ; ++i){ // for循序,dp[i]如果是true意思是说前i个串匹配到
for(int j = 0 ; j < i ; ++j){
if(dp[j] && wordDictSet.find(s.substr(j,i-j)) != wordDictSet.end()){
dp[i] = true;
break;//如果匹配到就跳出这个循环,继续下一个i
}
}
}
return dp[len];
}
};
动态规划代码