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 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1: 输入: s "leetcode",…...
Shell脚本编程
Shell编程 视频地址https://www.bilibili.com/video/BV1hW41167NW/?p1&vd_source977d52a6b92ce8b6ae67c16fc61f0428 第一章 Shell概述 大数据程序员为什么要学习Shell呢? 需要看懂运维人员编写的Shell程序偶尔会编写一些简单的Shell程序来管理集群…...
ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码
ChatGPT解答:JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2,给出详细的方案和代码 ChatGPTDemo Based on OpenAI API (gpt-3.5-turbo). JavaScript保存当前网页页面图片为pdf文件或者word文件,前端用vue2&am…...
Python基础学习11——文件
我们可以利用python对本电脑文件夹里的文件进行处理,python中提供了一系列相关的方法和函数供我们使用。 读取文件 我们现在在本python文件中有一个txt文件名为Lego,那么我们就可以利用python打开该文件 with open(Lego.txt) as file_text:contents …...
外网用户打不开公司的网站?web服务器端口映射到公网
我们经常会遇到这样的情景,在公司内部可以打开公司的网站,在家里或者外网却打不开,按照网上的做法,重新启动了服务器和iis,还是不行。许多用户设置了路由器端口映射功能,但是端口映射不成功怎么办ÿ…...
【CS224W】(task9)图神经网络的表示能力(更新中!!)
note 基于图同构网络(GIN)的图表征网络。为了得到图表征首先需要做节点表征,然后做图读出。GIN中节点表征的计算遵循WL Test算法中节点标签的更新方法,因此它的上界是WL Test算法。 在图读出中,我们对所有的节点表征&…...
binlog找回误删数据
1、检查当前是否开启binlog存储 输入命令show variables like %log_bin%;,结果如下 可以看到log_bin的值是ON,说明binlog开启了。 2、查找binlog的存储位置 这个去到数据库的my.cnf配置文件中寻找,有一个log_bin的配置 切换到log_bin的目…...
《程序员面试金典(第6版)》面试题 02.03. 删除中间节点
题目描述 若链表中的某个节点,既不是链表头节点,也不是链表尾节点,则称其为该链表的「中间节点」。 假定已知链表的某一个中间节点,请实现一种算法,将该节点从链表中删除。 例如: 传入节点 c(…...
Spring Boot
目录 SpringBoot SpringBoot创建和使用 什么是Spring Boot Spring Boot优点 Spring Boot项目的创建 项目目录介绍和运行 目录介绍 项目运行 SpringBoot核心设计思想 SpringBoot的配置文件 配置文件的作用 配置文件的格式 注意事项 properties配置文件 propertie…...
图论初入门
目录 一、前言 二、图的概念 三、例题及相关概念 1、全球变暖(2018年省赛,lanqiao0J题号178) 2、欧拉路径 3、小例题 4、例题(洛谷P7771) 一、前言 本文主要讲了树与图的基本概念,图的存储、DFS遍历…...
02-Oracle数据库的启动与关闭
本文章主要讲解Oracle数据库的启动与关闭方法,详细讲解启动Oracle的命令,三种启动数据库的方法及区别;关闭数据库的4种方法及他们的区别。 启动和关闭数据库 •数据库没启动前,只有拥有DBA权限或者以sysoper或sysdba身份才能连接到…...
网络营销培训完能达到什么水平?学完能创业吗?
网络营销本身就是一门创业的技术,很多人学习网络营销,往往担心学完以后技术达不到,再工作几年才可以创业,实际这是错误的理解,那么,网络营销培训完能达到什么水平?新手学员参加网络营销培训&…...
大数据技术之——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模型系列文章中,我们构建了Size因子、Beta因子、Momentum因子和Residual Volatility因子,并分别创建了对应的单因子策略,本节文章在该系列下进一步构建NonLinear Size因子。从回测结果看,自2022年以来&…...
C++ 常用命令行开发工具(Linux)
文章目录1、简介2、gcc / g2.1 system(执行shell 命令)2.2 popen(建立管道I/O)2.3 vforkexec(新建子进程)3、clang3.1 下载和安装clang3.2 clang和gcc比较3.2.1 gcc3.2.2 clang3.2.3 LLVM4、make4.1 例子14…...
java基础学习 day47(抽象类,抽象方法)
1. 抽象方法 将共性的行为(方法)抽取到父类之后,由于每一个子类执行的内容是不一样的,所以,在父类中不能确定具体的方法体,该方法就可以定义为抽象方法。抽象方法定义格式: public abstract 返…...
Java代码弱点与修复之——Open redirect(开放重定向)
弱点描述 Open redirect , 开放重定向,是一种常见的安全漏洞,也被称为“重定向漏洞”。该漏洞通常出现在 Web 应用程序中,攻击者可以利用它将用户重定向到恶意站点,从而进行钓鱼攻击、恶意软件传播、诱骗等活动。 在 Java 中,通过重定向 HTTP 请求来实现应用程序中的跳转…...
Go 指针
指针在编程中,一个内存地址用来定位一段内存。通常地,一个内存地址用一个操作系统原生字(native word)来存储。 一个原生字在32位操作系统上占4个字节,在64位操作系统上占8个字节。 所以,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全景直播技术引领新媒体时代”
随着虚拟现实技术的不断发展,VR全景直播已经成为了越来越受欢迎的直播形式。VR全景直播可以让观众通过虚拟现实设备亲临直播现场,享受身临其境的观看体验。VR全景直播是什么? VR全景直播是虚拟现实技术和直播的结合。相对于传统直播ÿ…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
