当前位置: 首页 > news >正文

day39|139.单词拆分 背包问题ending

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 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、确定dp数组以及下标的含义

dp[j]:拆分字符串的长度为j,dp[j]=true表示可以拆分为一个或多个字典中出现的单词。

2、确定递推公式

完全背包,重复利用物品,且为排列数

字符串为背包,单词为物品,截字符串(j-len,j)看是否是一个单词,并且他的前序子串也是一个或多个单词,也就是判断是否为true

所以递推公式为:

if(j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j)))就为true

3、dp数组初始化

初始化dp[0]=true,否则所有都为false

4、确定遍历顺序

本题要求是排列数,有顺序要求

5、打印dp数组

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp=new boolean[s.length()+1];//有空字符串dp[0]=true;for (int j=1;j<=s.length();j++){for (String word:wordDict){int len=word.length();if (j>=len&&dp[j-len]&&word.equals(s.substring(j-len,j))){dp[j]=true;break;}}}/*  for (int j=1;j<=s.length();j++){System.out.print(dp[j]+" ");}*/return dp[s.length()];}
}

相关文章:

day39|139.单词拆分 背包问题ending

139.单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 示例 1&#xff1a; 输入: s "leetcode",…...

Shell脚本编程

Shell编程 视频地址https://www.bilibili.com/video/BV1hW41167NW/?p1&vd_source977d52a6b92ce8b6ae67c16fc61f0428 第一章 Shell概述 大数据程序员为什么要学习Shell呢&#xff1f; 需要看懂运维人员编写的Shell程序偶尔会编写一些简单的Shell程序来管理集群&#xf…...

ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码

ChatGPT解答&#xff1a;JavaScript保存当前网页页面图片为pdf文件或者word文件&#xff0c;前端用vue2&#xff0c;给出详细的方案和代码 ChatGPTDemo Based on OpenAI API (gpt-3.5-turbo). JavaScript保存当前网页页面图片为pdf文件或者word文件&#xff0c;前端用vue2&am…...

Python基础学习11——文件

我们可以利用python对本电脑文件夹里的文件进行处理&#xff0c;python中提供了一系列相关的方法和函数供我们使用。 读取文件 我们现在在本python文件中有一个txt文件名为Lego&#xff0c;那么我们就可以利用python打开该文件 with open(Lego.txt) as file_text:contents …...

外网用户打不开公司的网站?web服务器端口映射到公网

我们经常会遇到这样的情景&#xff0c;在公司内部可以打开公司的网站&#xff0c;在家里或者外网却打不开&#xff0c;按照网上的做法&#xff0c;重新启动了服务器和iis&#xff0c;还是不行。许多用户设置了路由器端口映射功能&#xff0c;但是端口映射不成功怎么办&#xff…...

【CS224W】(task9)图神经网络的表示能力(更新中!!)

note 基于图同构网络&#xff08;GIN&#xff09;的图表征网络。为了得到图表征首先需要做节点表征&#xff0c;然后做图读出。GIN中节点表征的计算遵循WL Test算法中节点标签的更新方法&#xff0c;因此它的上界是WL Test算法。 在图读出中&#xff0c;我们对所有的节点表征&…...

binlog找回误删数据

1、检查当前是否开启binlog存储 输入命令show variables like %log_bin%;&#xff0c;结果如下 可以看到log_bin的值是ON&#xff0c;说明binlog开启了。 2、查找binlog的存储位置 这个去到数据库的my.cnf配置文件中寻找&#xff0c;有一个log_bin的配置 切换到log_bin的目…...

《程序员面试金典(第6版)》面试题 02.03. 删除中间节点

题目描述 若链表中的某个节点&#xff0c;既不是链表头节点&#xff0c;也不是链表尾节点&#xff0c;则称其为该链表的「中间节点」。 假定已知链表的某一个中间节点&#xff0c;请实现一种算法&#xff0c;将该节点从链表中删除。 例如&#xff1a; 传入节点 c&#xff08…...

Spring Boot

目录 SpringBoot SpringBoot创建和使用 什么是Spring Boot Spring Boot优点 Spring Boot项目的创建 项目目录介绍和运行 目录介绍 项目运行 SpringBoot核心设计思想 SpringBoot的配置文件 配置文件的作用 配置文件的格式 注意事项 properties配置文件 propertie…...

图论初入门

目录 一、前言 二、图的概念 三、例题及相关概念 1、全球变暖&#xff08;2018年省赛&#xff0c;lanqiao0J题号178&#xff09; 2、欧拉路径 3、小例题 4、例题&#xff08;洛谷P7771&#xff09; 一、前言 本文主要讲了树与图的基本概念&#xff0c;图的存储、DFS遍历…...

02-Oracle数据库的启动与关闭

本文章主要讲解Oracle数据库的启动与关闭方法&#xff0c;详细讲解启动Oracle的命令&#xff0c;三种启动数据库的方法及区别&#xff1b;关闭数据库的4种方法及他们的区别。 启动和关闭数据库 •数据库没启动前&#xff0c;只有拥有DBA权限或者以sysoper或sysdba身份才能连接到…...

网络营销培训完能达到什么水平?学完能创业吗?

网络营销本身就是一门创业的技术&#xff0c;很多人学习网络营销&#xff0c;往往担心学完以后技术达不到&#xff0c;再工作几年才可以创业&#xff0c;实际这是错误的理解&#xff0c;那么&#xff0c;网络营销培训完能达到什么水平&#xff1f;新手学员参加网络营销培训&…...

大数据技术之——zeppelin数据清洗

一、zeppelin的安装zeppelin解压后进入到conf配置文件界面。修改zeppelin-site.xml[roothadoop02 conf]# cp zeppelin-site.xml.template zeppelin-site.xml[roothadoop02 conf]# vim zeppelin-site.xml将IP地址和端口号设置成自己的修改 zeppelin-env.shexport JAVA HOME/opt/…...

Barra模型因子的构建及应用系列五之NonLinear Size因子

一、摘要 在前期的Barra模型系列文章中&#xff0c;我们构建了Size因子、Beta因子、Momentum因子和Residual Volatility因子&#xff0c;并分别创建了对应的单因子策略&#xff0c;本节文章在该系列下进一步构建NonLinear Size因子。从回测结果看&#xff0c;自2022年以来&…...

C++ 常用命令行开发工具(Linux)

文章目录1、简介2、gcc / g2.1 system&#xff08;执行shell 命令&#xff09;2.2 popen&#xff08;建立管道I/O&#xff09;2.3 vforkexec&#xff08;新建子进程&#xff09;3、clang3.1 下载和安装clang3.2 clang和gcc比较3.2.1 gcc3.2.2 clang3.2.3 LLVM4、make4.1 例子14…...

java基础学习 day47(抽象类,抽象方法)

1. 抽象方法 将共性的行为&#xff08;方法&#xff09;抽取到父类之后&#xff0c;由于每一个子类执行的内容是不一样的&#xff0c;所以&#xff0c;在父类中不能确定具体的方法体&#xff0c;该方法就可以定义为抽象方法。抽象方法定义格式&#xff1a; public abstract 返…...

Java代码弱点与修复之——Open redirect(开放重定向)

弱点描述 Open redirect , 开放重定向,是一种常见的安全漏洞,也被称为“重定向漏洞”。该漏洞通常出现在 Web 应用程序中,攻击者可以利用它将用户重定向到恶意站点,从而进行钓鱼攻击、恶意软件传播、诱骗等活动。 在 Java 中,通过重定向 HTTP 请求来实现应用程序中的跳转…...

Go 指针

指针在编程中&#xff0c;一个内存地址用来定位一段内存。通常地&#xff0c;一个内存地址用一个操作系统原生字&#xff08;native word&#xff09;来存储。 一个原生字在32位操作系统上占4个字节&#xff0c;在64位操作系统上占8个字节。 所以&#xff0c;32位操作系统上的理…...

shardingsphere5.1.1分表分库yaml配置 自定义策略

前言通过阅读官方稳定给出示例 https://shardingsphere.apache.org/document一、基本配置示例spring:sharding:datasource:names: ds0, ds1ds0:driver-class-name: com.mysql.jdbc.Driverurl: jdbc:mysql://localhost:3306/db0username: rootpassword: rootds1:driver-class-na…...

“探索未来:VR全景直播技术引领新媒体时代”

随着虚拟现实技术的不断发展&#xff0c;VR全景直播已经成为了越来越受欢迎的直播形式。VR全景直播可以让观众通过虚拟现实设备亲临直播现场&#xff0c;享受身临其境的观看体验。VR全景直播是什么&#xff1f; VR全景直播是虚拟现实技术和直播的结合。相对于传统直播&#xff…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

接口 RESTful 中的超媒体:REST 架构的灵魂驱动

在 RESTful 架构中&#xff0c;** 超媒体&#xff08;Hypermedia&#xff09;** 是一个核心概念&#xff0c;它体现了 REST 的 “表述性状态转移&#xff08;Representational State Transfer&#xff09;” 的本质&#xff0c;也是区分 “真 RESTful API” 与 “伪 RESTful AP…...