当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...