一文刷题学懂(一维动态规划)——java+python——3/5

这篇具有很好参考价值的文章主要介绍了一文刷题学懂(一维动态规划)——java+python——3/5。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

三、单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2:
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意,你可以重复使用字典中的单词。

示例 3:
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

1.Java解答

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}




2.python解答

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        import functools
        @functools.lru_cache(None)
        def back_track(s):
            if(not s):
                return True
            res=False
            for i in range(1,len(s)+1):
                if(s[:i] in wordDict):
                    res=back_track(s[i:]) or res
            return res
        return back_track(s)



3.主要思想
动态规划思想文章来源地址https://www.toymoban.com/news/detail-842710.html

到了这里,关于一文刷题学懂(一维动态规划)——java+python——3/5的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 一维动态规划

    2024年01月23日
    浏览(46)
  • 动态规划—— 01背包问题(一维,二维)

    0-1背包问题是一个经典问题,特别是在算法和动态规划领域。问题是关于一个小偷,他有一个可以携带最大重量的背包,并且他有一组物品,其中每个物品都有自己的价值和重量。小偷希望在不超过背包所能承载的最大重量的情况下,最大化他从这些物品中获得的总价值。问

    2024年02月19日
    浏览(44)
  • class066 一维动态规划【算法】

    算法讲解066【必备】从递归入手一维动态规划 // 斐波那契数 // 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 // 该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。 // 也就是:F(0) = 0,F(1) = 1 // F(n) = F(n - 1) + F(n - 2),其中 n 1 // 给定 n ,请计算

    2024年02月04日
    浏览(34)
  • 一维动态规划经典力扣题目(一)

    目录 题一:斐波那契数列 题目二:最低票价 题三:解码方法 递归方法是2的n次方的时间复杂度。 递归代码: 带有缓存的递归,会使时间复杂度得到大幅度优化。 时间复杂度为O(n)。 缓存即记录中间值         优化的方法:         代码:         代码:

    2024年02月21日
    浏览(40)
  • 【leetcode100-086到090】【动态规划】一维五题合集2

    【单词拆分】 给你一个字符串  s  和一个字符串列表  wordDict  作为字典。如果可以利用字典中出现的一个或多个单词拼接出  s  则返回  true 。 注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 思路: 首先,我们依次考虑s的前i个字母能否被

    2024年02月19日
    浏览(37)
  • 从二维数组到一维数组——探索01背包问题的动态规划优化

    本文将继续上一篇博客爬楼梯之后继续讲解同样用到了动态规划的 01背包问题 在解决动态规划问题时,我们经常面临着空间复杂度的挑战。01背包问题是一个典型的例子,通常使用二维数组来表示状态转移,但这样会带来额外的空间开销。在本文中,我们将探讨如何通过优化

    2024年04月11日
    浏览(58)
  • Leetcode动态规划篇(0-1背包问题一维和二维dp实现)

    🤗专栏:每日算法学习 💬个人主页:个人主页 🤓情况描述:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。每一件物品其实只有两个状态,取或者不取。

    2023年04月09日
    浏览(41)
  • 【LeetCode动态规划#06】分割等和子集(01背包问题一维写法实战)

    分割等和子集 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 示例 2: 输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割

    2023年04月09日
    浏览(62)
  • 【LeetCode动态规划#07】01背包问题一维写法(状态压缩)实战,其二(目标和、零一和)

    力扣题目链接(opens new window) 难度:中等 给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例: 输入

    2023年04月18日
    浏览(60)
  • Leetcode 刷题 动态规划

    309. 最佳买卖股票时机含冷冻期 1. 确定dp数组以及下标的含义 具体可以区分出如下四个状态: 状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有) 不持有股票状态,这里就有两种卖出股票状态 状态二:保持卖出股票的状态(两天前就

    2024年02月11日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包