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

ComfyUI翻译节点终极指南:如何选择最适合你的AI创作翻译工具

ComfyUI翻译节点终极指南&#xff1a;如何选择最适合你的AI创作翻译工具 【免费下载链接】ComfyUI_Custom_Nodes_AlekPet Custom nodes that extend the capabilities of Comfyui 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI_Custom_Nodes_AlekPet 在AI图像生…...

基于历史数据的加密货币交易系统策略验证实践指南

基于历史数据的加密货币交易系统策略验证实践指南 【免费下载链接】node-binance-trader &#x1f4b0; Cryptocurrency Trading Strategy & Portfolio Management Development Framework for Binance. &#x1f916; 项目地址: https://gitcode.com/gh_mirrors/no/node-…...

别再踩坑了!KubeKey离线安装K8s v1.26.12时,containerd镜像拉取失败的完整避坑指南

KubeKey离线部署K8s集群&#xff1a;containerd镜像拉取全流程避坑手册 第一次用KubeKey离线部署Kubernetes集群时&#xff0c;containerd镜像拉取失败的问题让我折腾了大半天。看着部署日志里反复出现的证书错误提示&#xff0c;才意识到离线环境下的镜像仓库配置远比想象中复…...

小白也能学会:MogFace透明蒙版可视化,人脸检测不再难

小白也能学会&#xff1a;MogFace透明蒙版可视化&#xff0c;人脸检测不再难 1. 为什么需要透明蒙版可视化&#xff1f; 想象一下这样的场景&#xff1a;你拍了一张全家福&#xff0c;想用AI工具检测照片中有多少人。传统的检测工具会在每个人脸上画一个绿色的方框&#xff0…...

Pixel Aurora Engine快速部署:阿里云ECS轻量服务器一键安装脚本

Pixel Aurora Engine快速部署&#xff1a;阿里云ECS轻量服务器一键安装脚本 1. 像素极光引擎简介 Pixel Aurora&#xff08;像素极光&#xff09;是一款基于AI扩散模型的高端绘图工作站&#xff0c;采用独特的复古像素游戏风格界面设计。这款创意引擎能够将文字描述转化为极具…...

终极PDF批量处理指南:如何用PDF Arranger自动化文档操作

终极PDF批量处理指南&#xff1a;如何用PDF Arranger自动化文档操作 【免费下载链接】pdfarranger Small python-gtk application, which helps the user to merge or split PDF documents and rotate, crop and rearrange their pages using an interactive and intuitive gra…...

告别CTex!TeX Live+Texstudio组合安装避坑指南(Windows/Mac双平台)

告别CTex&#xff01;TeX LiveTexstudio组合安装避坑指南&#xff08;Windows/Mac双平台&#xff09; 如果你曾经使用过CTex套装&#xff0c;可能会被其"开箱即用"的便利性所吸引。但当你需要跨平台协作或追求更灵活的定制时&#xff0c;TeX LiveTexstudio的组合无疑…...

当仿真与FPGA打架时,你该信谁?

该文章同步至公众号OneChan 一、一个真实的故事&#xff1a;比特翻转的“罗生门” 去年&#xff0c;我们在做一款通信芯片的嵌入式固件开发。在仿真环境中&#xff0c;我们精心编写的DMA驱动完美无缺&#xff0c;数据传输的CRC校验次次通过。我们信心满满地把比特流下载到FPG…...

2026学生免费用AI编程神器全攻略——白嫖不要白不要,大学生快来

好的&#xff0c;上一章刚教你用GitHub武装自己&#xff0c;筑起技术护城河&#xff0c;但光会搬砖&#xff08;敲命令&#xff09;还不够&#xff0c;你得学会“开高达”——用AI编程助手把效率拉满。 2026年了&#xff0c;如果还纯靠手打for循环和查API文档&#xff0c;那你…...

小白也能玩转GLM-4V-9B:免费开源多模态模型部署全流程

小白也能玩转GLM-4V-9B&#xff1a;免费开源多模态模型部署全流程 1. 环境准备与快速部署 1.1 硬件要求与系统配置 GLM-4V-9B作为90亿参数的多模态模型&#xff0c;对硬件有一定要求&#xff1a; GPU推荐&#xff1a;至少24GB显存的显卡&#xff08;如RTX 4090&#xff09;…...