力扣 -- 139. 单词拆分

这篇具有很好参考价值的文章主要介绍了力扣 -- 139. 单词拆分。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

力扣 -- 139. 单词拆分,力扣动态规划,力扣经典面试题,leetcode,算法,职场和发展,c++,c语言,数据结构,动态规划

 题目链接:139. 单词拆分 - 力扣(LeetCode)

二、解题步骤

下面是用动态规划的思想解决这道题的过程,相信各位小伙伴都能看懂并且掌握这道经典的动规题目滴。

力扣 -- 139. 单词拆分,力扣动态规划,力扣经典面试题,leetcode,算法,职场和发展,c++,c语言,数据结构,动态规划

三、参考代码 

 

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n=s.size();
        vector<int> dp(n+1);
        s=' '+s;
        unordered_set<string> set;
        for(const auto& e:wordDict)
        {
            set.insert(e);
        }

        dp[0]=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                if(dp[j-1]&&set.count(s.substr(j,i-j+1)))
                {
                    dp[i]=true;
                    break;
                }
                else
                {
                    dp[i]=false;
                }
            }
        }

        return dp[n];
    }
};

以上就是用动态规划的思想分析这道题目的整个过程啦,你学会了吗?如果以上题解对你有所帮助,那么就点亮一下小心心,点点关注呗,后期还会持续更新动态规划的经典题目哦,我们下期见啦!!!!! !!!!文章来源地址https://www.toymoban.com/news/detail-631323.html

到了这里,关于力扣 -- 139. 单词拆分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣 139. 单词拆分

    给你一个字符串 s 和一个字符串列表 word_dict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意 :不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 通过 回溯法 进行 暴力 求解,时间复杂度 O ( n × 2 n ) O(n times 2^n) O ( n × 2 n ) ,空间

    2024年02月03日
    浏览(34)
  • Leetcode 139.单词拆分

    OJ链接 :139.单词拆分  代码:    

    2024年02月04日
    浏览(39)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(59)
  • leetcode 动态规划(单词拆分)

    139.单词拆分 力扣题目链接(opens new window) 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = “leetcode”

    2024年02月22日
    浏览(40)
  • 【LeetCode动态规划#10】完全背包问题实战,其三(单词拆分,涉及集合处理字符串)

    力扣题目链接(opens new window) 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = \\\"leetcode\\\", wordDict = [\\\"lee

    2023年04月20日
    浏览(58)
  • 力扣hot100 单词拆分 变形背包 排列

    Problem: 139. 单词拆分 👨‍🏫 参考题解 时间复杂度: O ( n 3 ) O(n^3) O ( n 3 )

    2024年01月20日
    浏览(41)
  • 力扣labuladong一刷day63天单词拆分

    力扣labuladong一刷day63天单词拆分 一、139. 单词拆分 题目链接:https://leetcode.cn/problems/word-break/description/ 思路:s是否能被拆分成字典中的单词,单词数量是不限的,故是完全背包问题,不限数量的单词是否能组成字符串s,可以看的出来,并不是要求你长度相等就可以,还得有

    2024年01月21日
    浏览(34)
  • LeetCode力扣 面试经典150题 详细题解 (1~5) 持续更新中

    目录 1.合并两个有序数组 2.移动元素  3.删除有序数组中的重复项  4.删除排序数组中的重复项 II 5.多数元素 暂时更新到这里,博主会持续更新的 题目(难度:简单): 给你两个按 非递减顺序 排列的整数数组  nums1   和  nums2 ,另有两个整数  m  和  n  ,分别表示  nu

    2024年02月19日
    浏览(41)
  • 【学会动态规划】单词拆分(24)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:139. 单词拆分 - 力扣(LeetCo

    2024年02月12日
    浏览(37)
  • 动态规划篇-06:单词拆分

    老样子,还是先尝试找出状态转移方程 对问题进行分解,尝试从子问题入手解决。 这也是前文提到过的 “分解问题” 的思想  对于输入的字符串 s,如果我能够从单词列表 wordDict 中找到一个单词匹配 s 的前缀 s[0..k],那么只要我能拼出 s[k+1..],就一定能拼出整个 s。换句话

    2024年01月22日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包