[LeetCode Hot 100] [动态编程] 单词分割
最编程
2024-04-20 10:04:05
...
题目链接:139. 单词拆分 - 力扣(LeetCode)
看能不能用字符串列表里面的字符串组成这个字符串,可以反复使用
即完全背包问题,同之前的完全平方数、零钱兑换,相当于给定几个数,可以反复用,看能不能组成某个数
定义dp[i]是目标字符串中以i为结尾的子串能不能由某个字符串word组成,如果可以,问题变成dp[i-word.size()]
此处组合需要考虑顺序,target遍历外层循环
class Solution {
public:
bool wordBreak(string s, vector<string> &wordDict) {
vector<bool> dp(s.size() + 1);
dp[0] = true;
for (int i = 1; i <= s.size(); ++i)
for (auto &word: wordDict) {
int n = word.size();
if (i - n >= 0 && s.substr(i - n, n) == word)
dp[i] = dp[i] || dp[i - n];
}
return dp[s.size()];
}
};
上一篇: 企业门户网站运营:改造