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

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...