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

HOT86-单词拆分

        leetcode原题链接:单词拆分

题目描述

       给你一个字符串 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 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅有小写英文字母组成
  • wordDict 中的所有字符串 互不相同

解题方法:动态规划。

1. 问题定义:dp[k]表示s[0,1,...,k-1],即以第k个字符结尾是否满足要求

2. 初始化:dp[0]=true,什么都不选,空也是一个集合的子集

3.状态转移方程: dp[i] = dp[j] && str[j, i-n]==true

4. 结果返回: dp[n]

C++代码

#include <iostream>
#include <string>
#include <vector>
#include <set>
/*
* dp[i]表示以s[0,1,...,i-1]是否满足要求
*     dp[i]= dp[i] || (dp[i-1] && s[i,...,n-1]在wordDict中
*/class Solution {
public:bool wordBreak(std::string s, std::vector<std::string>& wordDict) {int n = s.size();// 1. 问题定义:dp[k]表示s[0,1,...,k-1],即以第k个字符结尾是否满足要求std::vector<bool> dp(n+1, false); //dp[k]表示s[0,1,...,k-1],即以第k个字符结尾是否满足要求// 2. 初始化:dp[0]=true,什么都不选,空也是一个集合的子集dp[0] = true; //什么都不选,空也是一个集合的子集// 利用set保存词典,不用vector初始化std::set<std::string> word_set(wordDict.begin(), wordDict.end());// 3.状态转移方程: dp[i] = dp[j] && str[j, i-n]==truefor (int i = 1; i <= n; i++) { //从第1个字符,遍历到第n个字符// 用s[j]分割第i个字符结尾的字符串for (int j = 0; j < i; j++) { //std::string right_str = s.substr(j, i - j);if (dp[j] && word_set.count(right_str) > 0) { //只要找到一个分割点符合条件,说明字符串满足要求dp[i] = true;break;}}}// 4. 结果返回: dp[n]return dp[n];//返回以第n个字符结尾的字符串是否满足要求}
};

相关文章:

HOT86-单词拆分

leetcode原题链接&#xff1a;单词拆分 题目描述 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 示例 1&#xff1a…...

开源数据集分类汇总(医学,卫星,分割,分类,人脸,农业,姿势等)

本文汇总了医学图像、卫星图像、语义分割、自动驾驶、图像分类、人脸、农业、打架识别等多个方向的数据集资源&#xff0c;均附有下载链接。 该文章仅用于学习记录&#xff0c;禁止商业使用&#xff01; 1.医学图像 疟疾细胞图像数据集 下载链接&#xff1a;http://suo.nz/2V…...

Linux:Firewalld防火墙

目录 绪论 1、firewalld配置模式 2、预定义服务&#xff1a;系统自带 3端口管理 绪论 firewalld 防火墙&#xff0c;包过滤防火墙&#xff0c;工作在网络层&#xff0c;centos7自带的默认的防火墙 作用是为了取代iptables 1、firewalld配置模式 运行时配置 永久配置 i…...

mysql死锁;锁表排查

概述 有时候提前终止了navicat执行线程&#xff0c;但是实际mysql还在执行这个线程&#xff0c; 需要通过mysql本身去终止. mysql:8.0 三板斧第一斧 捞点网上线程现成的执行命令 1.查询是否锁表 show OPEN TABLES where In_use > 0;2.查询进程&#xff08;如果您有SUP…...

YAMLException: java.nio.charset.MalformedInputException: Input length = 1

springboot项目启动的时候提示这个错误&#xff1a;YAMLException: java.nio.charset.MalformedInputException: Input length 1 根据异常信息提示&#xff0c;是YAML文件有问题。 原因是yml配置文件的编码有问题。 需要修改项目的编码格式&#xff0c;一般统一为UTF-8。 或…...

无需求文档,保障测试质量的可行性做法

这篇文章&#xff0c;内容是&#xff1a;无需求文档的情况下&#xff0c;作为一个测试人员&#xff0c;应该如何做 &#xff0c;才能保障测试质量不出问题&#xff0c;以及如何不背锅 &#xff1f; 001 没有需求文档3种可能情况 &#xff1a; 1、公司都没产品经理&#xff0…...

SpringBoot项目学习笔记

第一章 SpringBoot有哪些优点&#xff1f; Spring Boot作为Java开发的框架和工具集&#xff0c;具有许多优点&#xff0c;这些优点有助于简化开发过程并提高效率。以下是一些主要的优点&#xff1a; 简化配置&#xff1a; Spring Boot采用约定优于配置的原则&#xff0c;通过自…...

如何在Vue表单处理中实现表单字段的文件下载

Vue.js 是一种流行的JavaScript框架&#xff0c;用于构建用户界面。在Vue应用中&#xff0c;我们经常需要处理表单操作&#xff0c;其中一个常见需求是实现文件下载。以下介绍如何在Vue表单处理中实现表单字段的文件下载&#xff0c;大家共同交流。 一、使用HTML的a标签实现文…...

SSL证书DV和OV的区别?

SSL证书是在互联网通信中保护数据传输安全的一种加密工具。它能够确保客户端和服务器之间的通信得以加密&#xff0c;防止第三方窃听或篡改信息。在选择SSL证书时&#xff0c;常见的有DV证书和OV证书&#xff0c;它们在验证标准和信任级别上有所不同。那么SSL证书DV和OV的有哪些…...

计算机竞赛 GRU的 电影评论情感分析 - python 深度学习 情感分类

1 前言 &#x1f525;学长分享优质竞赛项目&#xff0c;今天要分享的是 &#x1f6a9; GRU的 电影评论情感分析 - python 深度学习 情感分类 &#x1f947;学长这里给一个题目综合评分(每项满分5分) 难度系数&#xff1a;3分工作量&#xff1a;3分创新点&#xff1a;4分 这…...

论文阅读 - Neutral bots probe political bias on social media

论文链接&#xff1a;Neutral bots probe political bias on social media | EndNote Click 试图遏制滥用行为和错误信息的社交媒体平台被指责存在政治偏见。我们部署中立的社交机器人&#xff0c;它们开始关注 Twitter 上的不同新闻源&#xff0c;并跟踪它们以探究平台机制与用…...

Fabric系列 - 知识点整理

知识点 源码编译 主机编译 容器编译 手动部署(docker-compose) 单peer 多peer 中途加peer 多主机多peer 链码 语法, 接口 (go版) 命令行调用 ca server 在DApp中使用SDK调用 (js版) 部署的几个阶段 部署1排序和1节点, 1组织1通道 光部署能Dapp 带ca server (每个组织一个)…...

多目标优化算法之樽海鞘算法(MSSA)

樽海鞘算法的主要灵感是樽海鞘在海洋中航行和觅食时的群聚行为。相关文献表示&#xff0c;多目标优化之樽海鞘算法的结果表明&#xff0c;该算法可以逼近帕雷托最优解&#xff0c;收敛性和覆盖率高。 通过给SSA算法配备一个食物来源库来解决第一个问题。该存储库维护了到目前为…...

阿里云轻量应用服务器使用教程_创建配置_远程连接_网站上线

阿里云轻量应用服务器怎么使用&#xff1f;阿里云百科分享轻量应用服务器从选择创建、配置建站环境、轻量服务器应用服务器远程连接、开端口到网站上线全流程&#xff1a; 目录 阿里云轻量应用服务器使用教程 步骤一&#xff1a;购买一台轻量应用服务器 步骤二&#xff1a;…...

自监督学习的概念

Self-Supervised Learning (SSL)的主要思想是解决先验任务来学习特征提取器&#xff0c;在不使用标签的情况下生成有用的表示。 这里先验任务是指&#xff0c; 先使用原始数据和特征提取器来提取出 数据的有效表示&#xff0e; 对比方法(即对比学习&#xff0c; Contrastiv…...

C#多线程开发详解

C#多线程开发详解 持续更新中。。。。。一、为什么要使用多线程开发1.提高性能2.响应性3.资源利用4.任务分解5.并行计算6.实时处理 二、多线程开发缺点1.竞态条件2.死锁和饥饿3.调试复杂性4.上下文切换开销5.线程安全性 三、多线程开发涉及的相关概念常用概念(1)lock(2)查看当前…...

Linux 基础篇(六)sudo和添加信任用户

一、sudo 1.是什么&#xff1f; 给被信任的普通用户授权&#xff0c;让被信任的普通用户能执行root用户才能执行的命令的一个命令。 2.为什么&#xff1f; 很多时候我们要在被信任的普通用户下执行一些root用户才能执行的命令&#xff0c;如 yum… 所以需要有一个命令能给普通用…...

【Linux】程序地址空间

程序地址空间 首先引入地址空间的作用什么是地址空间为什么要有地址空间 首先引入地址空间的作用 1 #include <stdio.h>2 #include <unistd.h>3 #include <stdlib.h>4 int g_val 100;6 int main()7 {8 pid_t id fork();9 if(id 0)10 {11 int cn…...

springboot 设置自定义启动banner背景图 教程

springboot banner Spring Boot中的banner是在应用程序启动时显示的一个ASCII艺术字符或文本。它被用来给用户展示一些关于应用程序的信息&#xff0c;例如名称、版本号或者公司标志等。 使用Spring Boot的默认设置&#xff0c;如果项目中有一个名为“banner.txt”的文件放置…...

CSS的引入方式有哪些?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 内联样式&#xff08;Inline Styles&#xff09;⭐ 内部样式表&#xff08;Internal Stylesheet&#xff09;⭐ 外部样式表&#xff08;External Stylesheet&#xff09;⭐ 导入样式表&#xff08;Import Stylesheet&#xff09;⭐ 写在最…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist

现象&#xff1a; android studio报错&#xff1a; [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决&#xff1a; 不要动CMakeLists.…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...