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

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...