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

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.打印数组:

139.单词拆分

 

代码实现

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.单词拆分 题目链接&#xff1a;139. 单词拆分 - 力扣&#xff08;LeetCode&#xff09; 视频链接&#xff1a;动态规划之完全背包&#xff0c;你的背包如何装满&#xff1f;| LeetCode&#xff1a;139.单词拆分_哔哩哔哩_bilibili 题目概述 给你一个字符串 s 和一…...

深入理解高并发编程 - Thread 类的 stop () 和 interrupt ()

stop() stop() 方法被用于停止线程。然而&#xff0c;需要注意的是&#xff0c;stop() 方法已经被标记为已废弃&#xff08;deprecated&#xff09;&#xff0c;并且不推荐使用。这是因为使用该方法可能导致不可预料的问题和数据不一致性&#xff0c;因此它被认为是不安全的。…...

C语言之三子棋游戏实现篇

目录 主函数test.c 菜单函数 选择实现 游戏函数 &#xff08;函数调用&#xff09; 打印棋盘数据 打印展示棋盘 玩家下棋 电脑下棋 判断输赢 循环 test.c总代码 头文件&函数声明game.h 头文件的包含 游戏符号声明 游戏函数声明 game.h总代码 游戏函数ga…...

jupyter notebook 插件nbextensions的安装

安装步骤&#xff1a; 1、打开 jupyter notebook&#xff0c;新建一个 python 文件&#xff1b; 2、 分别输入以下代码&#xff0c;然后运行&#xff0c;出现 warning 不影响使用&#xff0c;如果出现 errors&#xff0c;则说明下载有问题&#xff1a; !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实现贪吃蛇小游戏

文章目录&#xff1a; 一&#xff1a;效果演示 二&#xff1a;实现思路 三&#xff1a;代码实现 widget.h widget.cpp main.cpp 一&#xff1a;效果演示 效果图◕‿◕✌✌✌ 代码下载 二&#xff1a;实现思路 通过按键控制蛇的移动&#xff0c;每吃一个商品蛇身就会加长…...

Spring Boot整合RabbitMQ之路由模式(Direct)

RabbitMQ中的路由模式&#xff08;Direct模式&#xff09;应该是在实际工作中运用的比较多的一种模式了&#xff0c;这个模式和发布与订阅模式的区别在于路由模式需要有一个routingKey&#xff0c;在配置上&#xff0c;交换机类型需要注入DirectExchange类型的交换机bean对象。…...

行式存储与列式存储

1.概述 数据处理大致可分为两大类&#xff0c;联机事务处理OLTP(on-line transaction processing) 和联机分析处理OLAP(on-line analytical processing)。 OLTP是传统关系型数据库的主要应用&#xff0c;用来执行一些基本的、日常的事务处理&#xff0c;比如数据库记录的增、删…...

windows上sqlserver的ldf日志文件和数据mdf文件分别放到不同的磁盘

之前我的windows上已安装好了sqlserver2017&#xff0c;有一个名为TestDb的数据库。ldf文件和mdf文件都一起放在D:\Database目录下。现在需要把ldf日志文件到E盘的database目录下。 重要的事情先说三遍 先停止网关&#xff08;例如nginx&#xff09;并备份数据库 先停止网关&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框架&#xff0c;而Spring是一个全栈式的框架&#xff0c;二者的结合可以让我们更加高效地进行数据持久化操作。 Mybatis与Spring的集成主要有两种方式&#xff1a;使用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 运行如下指令即可&#xff1a; Set-…...

Dockerfile快速搭建自己专属的LAMP环境,生成镜像lamp:v1.1,并推送到私有仓库

环境&#xff1a; CentOS 7 Linux 3.10.0-1160.el7.x86_64 具体要求如下&#xff1a; &#xff08;1&#xff09;基于centos:6基础镜像&#xff1b; &#xff08;2&#xff09;指定作者信息&#xff1b; &#xff08;3&#xff09;安装httpd、mysql、mysql-server、php、ph…...

Lottery抽奖项目学习第二章第一节:环境、配置、规范

Lottery抽奖项目学习第二章第一节&#xff1a;环境、配置、规范 环境、配置、规范 下面以DDD架构和设计模式落地实战的方式&#xff0c;进行讲解和实现分布式抽奖系统的代码开发&#xff0c;那么这里会涉及到很多DDD的设计思路和设计模式应用&#xff0c;以及互联网大厂开发中…...

OpenCV之reshape函数

函数原型&#xff1a; /** 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事务&#xff08;2&#xff09; 文章目录 【JavaEE】Spring事务&#xff08;2&#xff09;1. Transactional 参数介绍1.1 value 和 transactionManager1.2 timeout1.3 readOnly1.4 后面四个1.5 isolation 与 propagation 2. Spring 事务隔离级别 - isolation2.…...

微信小程序canvas type=2d生成海报保存到相册、文字换行溢出显示...、文字删除线、分享面板

一、简介 做个简单的生成二维码海报分享&#xff0c;我做的时候也找简单的方法看能不能实现页面直接截图那种生成图片&#xff0c;原生小程序不支持&#xff0c;不多介绍下面有全部代码有注释、参数自行替换运行看看&#xff0c;还有需要优化的地方&#xff0c;有问题可以咨询…...

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:&…...

OpCore-Simplify:黑苹果配置的终极简化方案——从复杂到简单的革命性转变

OpCore-Simplify&#xff1a;黑苹果配置的终极简化方案——从复杂到简单的革命性转变 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 你是否曾经因为黑…...

Ostrakon-VL像素终端实战:为盲人顾客生成语音版货架导航

Ostrakon-VL像素终端实战&#xff1a;为盲人顾客生成语音版货架导航 1. 项目背景与价值 在零售场景中&#xff0c;视觉障碍顾客常常面临难以独立寻找商品的困境。传统解决方案依赖人工引导或专用盲道&#xff0c;成本高且灵活性不足。我们基于Ostrakon-VL-8B多模态大模型&…...

Path of Building PoE2:零基础掌握流放之路2角色规划工具实战指南

Path of Building PoE2&#xff1a;零基础掌握流放之路2角色规划工具实战指南 【免费下载链接】PathOfBuilding-PoE2 项目地址: https://gitcode.com/GitHub_Trending/pa/PathOfBuilding-PoE2 你是否曾遇到这样的困境&#xff1a;花费数小时规划的角色build&#xff0c…...

CVE-2024-36401复现

一.漏洞概述 CVE-2024-36401 是 GeoServer 中的一个严重级远程代码执行漏洞&#xff08;CVSS 9.8&#xff09;&#xff0c;允许未经身份验证的远程攻击者在服务器上执行任意代码。该漏洞源于 GeoServer 调用的 GeoTools 库 API 在评估 XPath 表达式时存在不安全处理&#xff0…...

SDXL 1.0插件开发:Photoshop脚本自动化集成

SDXL 1.0插件开发&#xff1a;Photoshop脚本自动化集成 1. 为什么需要Photoshop与SDXL 1.0的深度协作 设计师每天面对的不是单一工具&#xff0c;而是一整套工作流。当AI生成图像成为创意起点&#xff0c;问题就来了&#xff1a;生成的图片如何快速进入专业设计环节&#xff…...

从云端到指尖:巧用Aspose组件实现Office/PDF文档秒级HTML预览,攻克移动端大文件访问瓶颈

1. 移动端大文件预览的痛点与解决思路 最近接手一个企业级项目时&#xff0c;遇到了一个非常典型的场景&#xff1a;用户通过PC端上传各种办公文档&#xff08;Word、Excel、PPT、PDF&#xff09;&#xff0c;需要在移动端随时查看。但当文件体积较大时&#xff08;比如超过50M…...

Gemma-3 Pixel Studio一文详解:Flash Attention 2对图文响应速度提升实测

Gemma-3 Pixel Studio一文详解&#xff1a;Flash Attention 2对图文响应速度提升实测 1. 引言 在当今多模态AI应用快速发展的背景下&#xff0c;Gemma-3 Pixel Studio作为一款基于Google最新开源Gemma-3-12b-it模型构建的高性能对话终端&#xff0c;凭借其卓越的视觉理解能力…...

电话号码定位开源工具实战完全指南:从部署到企业应用

电话号码定位开源工具实战完全指南&#xff1a;从部署到企业应用 【免费下载链接】location-to-phone-number This a project to search a location of a specified phone number, and locate the map to the phone number location. 项目地址: https://gitcode.com/gh_mirro…...

Qwen3.5-9B自动化:GitHub Actions触发模型推理+PR评论生成

Qwen3.5-9B自动化&#xff1a;GitHub Actions触发模型推理PR评论生成 1. 项目概述 Qwen3.5-9B是一个拥有90亿参数的开源大语言模型&#xff0c;具备强大的逻辑推理、代码生成和多轮对话能力。最新版本还支持多模态理解&#xff08;图文输入&#xff09;和长达128K tokens的上…...

Mojo嵌入Python项目的4种架构模式(含GIL绕过实测数据+内存安全验证报告)

第一章&#xff1a;Mojo嵌入Python项目的4种架构模式&#xff08;含GIL绕过实测数据内存安全验证报告&#xff09;Mojo 作为兼具 Python 兼容性与系统级性能的新兴语言&#xff0c;其嵌入 Python 项目的能力已通过多种生产就绪架构得到验证。以下四种主流集成模式均在 macOS Ve…...