首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >Leetcode|完全背包|139. 单词拆分

Leetcode|完全背包|139. 单词拆分

作者头像
SL_World
发布于 2021-09-18 16:43:31
发布于 2021-09-18 16:43:31
5860
举报
文章被收录于专栏:XX

1 动态规划(完全背包)

基于问题本身,先背包后物品的顺序比较方便,也好理解

代码语言:javascript
复制
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int bagSize = s.size();
        vector<bool> dp(bagSize + 1, false);
        dp[0] = true;
        for (int j = 1; j <= bagSize; j++)               // 背包容量
            for (int i = 0; i < wordDict.size(); i++) {  // 物品
                int dictLen = wordDict[i].size();
                if (j >= dictLen && wordDict[i] == s.substr(j - dictLen, dictLen))
                    dp[j] = dp[j] || dp[j - dictLen];
            }   
        return dp[bagSize];
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/03/22 ,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • 1 动态规划(完全背包)
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档