LeetCode-139. 单词拆分【字典树 记忆化搜索 数组 哈希表 字符串 动态规划】

LeetCode-139. 单词拆分【字典树 记忆化搜索 数组 哈希表 字符串 动态规划】

  • 题目描述:
  • 解题思路一:Python动态规划五部曲:定推初遍举【先遍历背包 后遍历物品】必须是排列
  • 解题思路二:Python动态规划版本二
  • 解题思路三:回溯

题目描述:

给你一个字符串 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 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

解题思路一:Python动态规划五部曲:定推初遍举【先遍历背包 后遍历物品】必须是排列

【先遍历物品 后遍历背包】是组合,不可用

  1. 确定dp数组以及下标的含义
    dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。

  2. 确定递推公式
    如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  1. dp数组如何初始化
    从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。

那么dp[0]有没有意义呢?

dp[0]表示如果字符串为空的话,说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

  1. 确定遍历顺序
    题目中说是拆分为一个或多个在字典中出现的单词,所以这是完全背包。

还要讨论两层for循环的前后顺序。

如果求组合数就是外层for循环遍历物品,内层for遍历背包。

如果求排列数就是外层for遍历背包,内层for循环遍历物品。

我在这里做一个总结:

求组合数:动态规划:518.零钱兑换II (opens new window)求排列数:动态规划:377. 组合总和 Ⅳ (opens new window)、动态规划:70. 爬楼梯进阶版(完全背包) (opens new window)求最小数:动态规划:322. 零钱兑换 (opens new window)、动态规划:279.完全平方数(opens new window)

而本题其实我们求的是排列数,为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。

“apple”, “pen” 是物品,那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的,那么我们就是强调物品之间顺序。

所以说,本题一定是 先遍历 背包,再遍历物品。

  1. 举例推导dp[i]
    以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例,dp状态如图:
    在这里插入图片描述
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(1, len(s) + 1):
            for word in wordDict:
                if i >= len(word):
                    dp[i] = dp[i] or (dp[i-len(word)] and s[i-len(word):i] == word)
        return dp[len(s)]

时间复杂度:O(n3)
空间复杂度:O(n)

解题思路二:Python动态规划版本二

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)  # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词
        dp[0] = True  # 初始状态,空字符串可以被拆分成单词

        for i in range(1, n + 1): # 遍历背包
            for j in range(i): # 遍历单词
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True  # 如果 s[0:j] 可以被拆分成单词,并且 s[j:i] 在单词集合中存在,则 s[0:i] 可以被拆分成单词
                    break

        return dp[n]

时间复杂度:O(n3)
空间复杂度:O(n)

解题思路三:回溯

class Solution:
    def backtracking(self, s: str, wordSet: set[str], startIndex: int) -> bool:
        # 边界情况:已经遍历到字符串末尾,返回True
        if startIndex >= len(s):
            return True

        # 遍历所有可能的拆分位置
        for i in range(startIndex, len(s)):
            word = s[startIndex:i + 1]  # 截取子串
            if word in wordSet and self.backtracking(s, wordSet, i + 1):
                # 如果截取的子串在字典中,并且后续部分也可以被拆分成单词,返回True
                return True

        # 无法进行有效拆分,返回False
        return False

    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)  # 转换为哈希集合,提高查找效率
        return self.backtracking(s, wordSet, 0)

时间复杂度:O(n3)
空间复杂度:O(n2) # 递归

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/529082.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

tensorflow.js 使用 opencv.js 将人脸特征点网格绘制与姿态估计线绘制结合起来,以获得更高的帧数

系列文章目录 如何在前端项目中使用opencv.js | opencv.js入门如何使用tensorflow.js实现面部特征点检测tensorflow.js 如何从 public 路径加载人脸特征点检测模型tensorflow.js 如何使用opencv.js通过面部特征点估算脸部姿态并绘制示意图 文章目录 系列文章目录前言一、实现步…

实验:基于Red Hat Enterprise Linux系统建立逻辑卷并进行划分

目录 一. 实验目的 二. 实验内容 三. 实验设计描述及实验结果 1. 为虚拟机添加三块大小为5GB的磁盘nvme0n2 nvme0n3 nvme0n4 2. 将三块硬盘转换为物理卷&#xff0c;并将nvme0n2 nvme0n3两pv建立成名为"自己名字_vg“的卷组&#xff0c;并将nvme0n4扩展进该卷组。 LVM管…

基于单片机四路继电器温湿度控制

**单片机设计介绍&#xff0c; 基于单片机四路继电器温湿度控制 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机四路继电器温湿度控制的设计是一种能够实现精确环境调控的智能化系统。它利用单片机作为核心控制器&…

渗透测试面试题汇总(全)

思路流程 信息收集漏洞挖掘漏洞利用&权限提升清除测试数据&输出报告复测 问题深信服一面:SQL注入防护为什么参数化查询可以防止sql注入SQL头注入点盲注是什么&#xff1f;怎么盲注&#xff1f;宽字节注入产生原理以及根本原因 产生原理在哪里编码根本原因解决办法sql里…

力扣刷题Days33-274. H 指数(js)

目录 1&#xff0c;题目 2&#xff0c;代码 2.1排序 2.2计数排序 3&#xff0c;学习与总结 3.1排序实现的学习总结 3.2计数排序的学习总结 1&#xff0c;题目 给你一个整数数组 citations &#xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返…

Java 线程池 参数

1、为什么要使用线程池 线程池能有效管控线程&#xff0c;统一分配任务&#xff0c;优化资源使用。 2、线程池的参数 创建线程池&#xff0c;在构造一个新的线程池时&#xff0c;必须满足下面的条件&#xff1a; corePoolSize&#xff08;线程池基本大小&#xff09;必须大于…

1.Spring的核心思想 —— IOC和DI

1. Spring是什么&#xff1f; 简单的说&#xff0c;Spring其实指的是Spring Framework&#xff08;Spring框架&#xff09;&#xff0c;是一个开源框架。 如果要用一句话概括&#xff1a;它是包含众多工具方法的IOC&#xff08;Inverse of Control控制反转&#xff09;容器。…

【THM】Net Sec Challenge(网络安全挑战)-初级渗透测试

介绍 使用此挑战来测试您对网络安全模块中获得的技能的掌握程度。此挑战中的所有问题都可以仅使用nmap、telnet和来解决hydra。 挑战问题 您可以使用Nmap、 Telnet 和Hydra回答以下问题。 2.1小于10000的最大开放端口号是多少? 8080 nmap -p- -T4 10.10.234.218 2.2普通…

Java入门-java的方法

java方法 java的方法是用来完成某种功能的代码块。使用方法封装代码块&#xff0c;可以提高代码的可复用性&#xff0c;模块化&#xff0c;使用者无需知道代码的具体实现也能通过方法调用使用其提供的功能&#xff0c;简化了应用过程。 方法结构 一般一个方法的构成有如图几部…

【C++】vector问题解决(非法的间接寻址,迭代器失效 , memcpy拷贝问题)

送给大家一句话&#xff1a; 世界在旋转&#xff0c;我们跌跌撞撞前进&#xff0c;这就够了 —— 阿贝尔 加缪 vector问题解决 1 前言2 迭代器区间拷贝3 迭代器失效问题4 memcpy拷贝问题 1 前言 我们之前实现了手搓vector&#xff0c;但是当时依然有些问题没有解决&#xff…

HarmonyOS 开发-多模态页面转场动效实现案例

介绍 本示例介绍多模态页面转场动效实现&#xff1a;通过半模态转场实现半模态登录界面&#xff0c;通过配置NavDestinationMode类型为DIALOG&#xff0c;实现半模态的背景为透明&#xff0c;再与 全屏模态和组件转场结合实现多模态组合登录场景&#xff0c;其中手机验证码登录…

基于springboot+vue+Mysql的学习平台

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

【Web】CTFSHOW-2023CISCN国赛初赛刷题记录(全)

目录 Unzip BackendService go_session deserbug 主打一个精简 Unzip 进来先是一个文件上传界面 右键查看源码&#xff0c;actionupload.php 直接访问/upload.php&#xff0c;看到后端的源码 就是上传一个压缩包&#xff0c;对其进行解包处理 因为其是在/tmp下执行…

ip地址切换器安卓版,保护隐私,自由上网

在移动互联网时代&#xff0c;随着智能手机和平板电脑的普及&#xff0c;移动设备的网络连接变得愈发重要。为了满足用户在不同网络环境下的需求&#xff0c;IP地址切换器安卓版应运而生。本文将以虎观代理为例&#xff0c;为您详细解析IP地址切换器安卓版的功能、应用以及其所…

机器学习 基础 笔记 1

train阶段就是正常的学习 validation是知道正确答案是啥&#xff0c;检查正确率 test是不知道正确答案是啥&#xff0c;看看有啥结果 训练的时候记得model.train 测试&#xff08;后面两种都是&#xff09;的时候要model.eval &#xff08;有些模型两种阶段做的事不一样&a…

不要抱怨,不如抱 Java 运算符吧 (下篇)

本篇会加入个人的所谓鱼式疯言 ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人能接…

2024.4.9-day12-CSS 常用样式属性和字体图标

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 作业 作业 <!DOCTYPE html> <html lang"zh-CN"><he…

P4552 IncDec Sequence(差分)

题目描述 给定一个长度为 n n n 的数列 a 1 , a 2 , ⋯ , a n {a_1,a_2,\cdots,a_n} a1​,a2​,⋯,an​&#xff0c;每次可以选择一个区间 [ l , r ] [l,r] [l,r]&#xff0c;使这个区间内的数都加 1 1 1 或者都减 1 1 1。 请问至少需要多少次操作才能使数列中的所有数都…

rapidssl通配符证书760元

RapidSSL是Geotrust旗下的子品牌&#xff0c;旗下有两款基础型的数字证书产品——基础型单域名SSL证书和基础型通配符SSL证书。RapidSSL旗下的数字证书产品可以为个人或者企事业单位网站提供先进的加密算法和技术&#xff0c;确保网站数据在传输过程中不被窃取或篡改。今天就随…

Matlab|电价型负荷需求响应(考虑电价变化)

程序复现来源于《计及需求响应消纳风电的电-热综合能源系统经济调度 》第四章内容。 一、原理 需求响应的基本原理是需求侧根据电力市场价格和电网要求改变其负荷需求以 获取一定的利益回报。其中 PDR 可通过直观的电价变化信号引导用户调节用电方式&#xff0c; 从而达到优…