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:&…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...
