Day46|leetcode 139.单词拆分
leetcode 139.单词拆分
题目链接:139. 单词拆分 - 力扣(LeetCode)
视频链接:动态规划之完全背包,你的背包如何装满?| LeetCode:139.单词拆分_哔哩哔哩_bilibili
题目概述
给你一个字符串 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[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。
2.确定递推公式:
递推公式: if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
3.数组初始化:
dp[0]=true,其余的都初始化成false。
4.确定遍历顺序:
本题求的是排列数,先遍历背包后遍历物品。
为什么是排列数呢,例如:s="mom",wordDict="m","o".把m编号为1,把o编号为2,那么mom就是由编号1,2,1组成,而112和211都不行,讲究顺序,所以是排列数。
5.打印数组:

代码实现
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++) { // 遍历背包for (int j = 0; j < i; j++) { // 遍历物品string word = s.substr(j, i - j); //substr(起始位置,截取的个数)if (wordSet.find(word) != wordSet.end() && dp[j]) {dp[i] = true;}}}return dp[s.size()];}
};
相关文章:
Day46|leetcode 139.单词拆分
leetcode 139.单词拆分 题目链接:139. 单词拆分 - 力扣(LeetCode) 视频链接:动态规划之完全背包,你的背包如何装满?| LeetCode:139.单词拆分_哔哩哔哩_bilibili 题目概述 给你一个字符串 s 和一…...
深入理解高并发编程 - Thread 类的 stop () 和 interrupt ()
stop() stop() 方法被用于停止线程。然而,需要注意的是,stop() 方法已经被标记为已废弃(deprecated),并且不推荐使用。这是因为使用该方法可能导致不可预料的问题和数据不一致性,因此它被认为是不安全的。…...
C语言之三子棋游戏实现篇
目录 主函数test.c 菜单函数 选择实现 游戏函数 (函数调用) 打印棋盘数据 打印展示棋盘 玩家下棋 电脑下棋 判断输赢 循环 test.c总代码 头文件&函数声明game.h 头文件的包含 游戏符号声明 游戏函数声明 game.h总代码 游戏函数ga…...
jupyter notebook 插件nbextensions的安装
安装步骤: 1、打开 jupyter notebook,新建一个 python 文件; 2、 分别输入以下代码,然后运行,出现 warning 不影响使用,如果出现 errors,则说明下载有问题: !python -m pip install…...
Spring boot 集成单元测试
1.引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><scope>test</scope></dependency> 2. 3.编写测试类 package com.enterprise;import com.enterpr…...
基于C++的QT实现贪吃蛇小游戏
文章目录: 一:效果演示 二:实现思路 三:代码实现 widget.h widget.cpp main.cpp 一:效果演示 效果图◕‿◕✌✌✌ 代码下载 二:实现思路 通过按键控制蛇的移动,每吃一个商品蛇身就会加长…...
Spring Boot整合RabbitMQ之路由模式(Direct)
RabbitMQ中的路由模式(Direct模式)应该是在实际工作中运用的比较多的一种模式了,这个模式和发布与订阅模式的区别在于路由模式需要有一个routingKey,在配置上,交换机类型需要注入DirectExchange类型的交换机bean对象。…...
行式存储与列式存储
1.概述 数据处理大致可分为两大类,联机事务处理OLTP(on-line transaction processing) 和联机分析处理OLAP(on-line analytical processing)。 OLTP是传统关系型数据库的主要应用,用来执行一些基本的、日常的事务处理,比如数据库记录的增、删…...
windows上sqlserver的ldf日志文件和数据mdf文件分别放到不同的磁盘
之前我的windows上已安装好了sqlserver2017,有一个名为TestDb的数据库。ldf文件和mdf文件都一起放在D:\Database目录下。现在需要把ldf日志文件到E盘的database目录下。 重要的事情先说三遍 先停止网关(例如nginx)并备份数据库 先停止网关&am…...
vue3+uni——watch监听props中的数据(组件参数接收与传递defineProps、defineEmits)
案例说明 A页面引用的子组件B A页面 <template><view>//引用组件<serviceOrder change"change" :list"list" :current"type"></serviceOrder></view> </template><script setup>import serviceOrd…...
mybatis与spring集成与spring aop集成pagehelper插件
Mybatis与Spring的集成 Mybatis是一款轻量级的ORM框架,而Spring是一个全栈式的框架,二者的结合可以让我们更加高效地进行数据持久化操作。 Mybatis与Spring的集成主要有两种方式:使用Spring的Mybatis支持和使用Mybatis的Spring支持。 使用…...
Mybatis基础
...
TypeScript-- 配置Typescript环境(1)ts 转js,tsc --watch 实时编译
文章目录 安装Typescript判断是否有运行权限编写第一Typescript文件手动编译Ts文件转Js文件实时编译 安装Typescript npm install -g typescript 判断是否有运行权限 命令行运行 tsc -v 遇到了权限问题 用管理员打开window自带的powershell 运行如下指令即可: Set-…...
Dockerfile快速搭建自己专属的LAMP环境,生成镜像lamp:v1.1,并推送到私有仓库
环境: CentOS 7 Linux 3.10.0-1160.el7.x86_64 具体要求如下: (1)基于centos:6基础镜像; (2)指定作者信息; (3)安装httpd、mysql、mysql-server、php、ph…...
Lottery抽奖项目学习第二章第一节:环境、配置、规范
Lottery抽奖项目学习第二章第一节:环境、配置、规范 环境、配置、规范 下面以DDD架构和设计模式落地实战的方式,进行讲解和实现分布式抽奖系统的代码开发,那么这里会涉及到很多DDD的设计思路和设计模式应用,以及互联网大厂开发中…...
OpenCV之reshape函数
函数原型: /** brief Changes the shape and/or the number of channels of a 2D matrix without copying the data.The method makes a new matrix header for \*this elements. The new matrix may have a different sizeand/or different number of channels. A…...
【JavaEE】Spring事务-@Transactional参数介绍-事务的隔离级别以及传播机制
【JavaEE】Spring事务(2) 文章目录 【JavaEE】Spring事务(2)1. Transactional 参数介绍1.1 value 和 transactionManager1.2 timeout1.3 readOnly1.4 后面四个1.5 isolation 与 propagation 2. Spring 事务隔离级别 - isolation2.…...
微信小程序canvas type=2d生成海报保存到相册、文字换行溢出显示...、文字删除线、分享面板
一、简介 做个简单的生成二维码海报分享,我做的时候也找简单的方法看能不能实现页面直接截图那种生成图片,原生小程序不支持,不多介绍下面有全部代码有注释、参数自行替换运行看看,还有需要优化的地方,有问题可以咨询…...
C++卷积神经网络
C卷积神经网络 #include"TP_NNW.h" #include<iostream> #pragma warning(disable:4996) using namespace std; using namespace mnist;float* SGD(Weight* W1, Weight& W5, Weight& Wo, float** X) {Vector2 ve(28, 28);float* temp new float[10];V…...
go 读取yaml映射到struct
安装 go get gopkg.in/yaml.v3创建yaml Mysql:Host: 192.168.214.134Port: 3306UserName: wwPassword: wwDatabase: go_dbCharset: utf8mb4ParseTime: trueLoc: LocalListValue:- haha- test- vv JWTSecret: nidaye定义结构体 type Mysql struct {Host string yaml:&…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
redis和redission的区别
Redis 和 Redisson 是两个密切相关但又本质不同的技术,它们扮演着完全不同的角色: Redis: 内存数据库/数据结构存储 本质: 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能: 提供丰…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
2.2.2 ASPICE的需求分析
ASPICE的需求分析是汽车软件开发过程中至关重要的一环,它涉及到对需求进行详细分析、验证和确认,以确保软件产品能够满足客户和用户的需求。在ASPICE中,需求分析的关键步骤包括: 需求细化:将从需求收集阶段获得的高层需…...
基于stm32F10x 系列微控制器的智能电子琴(附完整项目源码、详细接线及讲解视频)
注:文章末尾网盘链接中自取成品使用演示视频、项目源码、项目文档 所用硬件:STM32F103C8T6、无源蜂鸣器、44矩阵键盘、flash存储模块、OLED显示屏、RGB三色灯、面包板、杜邦线、usb转ttl串口 stm32f103c8t6 面包板 …...
