【算法与数据结构】139、LeetCode单词拆分

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:本题可以看做一个动态规划问题。其中,字符串s是背包,而字典中的单词就是物品。题目问的是单词能否组成字符串s,就是问物品能不能把背包装满。字典中的单词可以重复使用,因此是一个完全背包问题。

  • 第一步, d p [ j ] dp[j] dp[j]的含义。 d p [ j ] dp[j] dp[j]代表的是字符串长度为 j j j时,该能否由字典中的单词构成。如果能,则为true。
  • 第二步,递推公式。如果确定 d p [ j ] dp[j] dp[j]是true,且 [ j , i ] [j, i] [j,i]这个区间的子串出现在字典里,那么 d p [ i ] dp[i] dp[i]一定是true。 ( j < i ) (j < i ) (j<i)。所以递推公式是:
    if(dp[j] &&  [j, i]这个区间的子串出现在字典里) dp[i] = true
    
  • 第三部,元素初始化。 d p [ 0 ] dp[0] dp[0]初始化为1。
  • 第四部,递归顺序。本题严格划分起来是一个排列问题。以s = “applepenapple”, wordDict = [“apple”, “pen”] 为例。我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的,那么我们就是强调物品之间顺序。所以说,本题一定是先遍历背包,再遍历物品
  • 第五步,打印结果。
      为了判断 [ j , i ] [j, i] [j,i]这个区间的子串出现在字典里,我们构建了一个无序集合。其底层实现是一个哈希表,可以在常数时间内( O ( 1 ) O(1) O(1))内进行查找。
      程序如下
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, 0);dp[0] = 1;for (int i = 1; i <= s.size(); i++) {	// 遍历背包(字符串s)for (int j = 0; j < i; j++) {		// 遍历物品(单词)string key = s.substr(j, i - j);if (dp[j] && wordSet.find(key) != wordSet.end()) {dp[i] = 1;}}}return dp[s.size()];}
};

复杂度分析:

  • 时间复杂度: O ( n 3 ) O(n^3) O(n3)。除了两层循环以外,还有需要substr返回子串,它是O(n)的复杂度(这里的n是substring的长度)。
  • 空间复杂度: O ( n ) O(n) O(n)

三、完整代码

# include <iostream>
# include <vector>
# include <string>
# include <unordered_set>
using namespace std;class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, 0);dp[0] = 1;for (int i = 1; i <= s.size(); i++) {	// 遍历背包(字符串s)for (int j = 0; j < i; j++) {		// 遍历物品(单词)string key = s.substr(j, i - j);if (dp[j] && wordSet.find(key) != wordSet.end()) {dp[i] = 1;}}}return dp[s.size()];}
};int main() {string s = "catsandog";vector<string> wordDict = { "cats", "dog", "sand", "and", "cat" };Solution s1;bool result = s1.wordBreak(s, wordDict);cout << result << endl;system("pause");return 0;
}

end

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/250346.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

指针的学习1

目录 什么是指针&#xff1f; 野指针 造成野指针的原因&#xff1a; 如何避免野指针&#xff1f; 内存和指针 如何理解编址&#xff1f; 指针变量和地址 取地址操作符& 指针变量和解引用操作符 指针变量 如何拆解指针类型&#xff1f; 指针变量的大小 指针变量…

麒麟系统—— openKylin 安装 Maven

麒麟系统—— openKylin 安装 Maven 一、准备工作1. 确保麒麟系统 openKylin 已经安装完毕。2. 确保 java 已经安装完毕 二、下载Maven三、解压 Maven 与环境配置解压配置环境变量验证 最终&#xff1a;介绍配置的其他参数使用 本文将分享如何在麒麟操作系统 openKylin 上安装…

【Spring源码分析】推断构造方法

推断构造方法源码解析 一、确认候选构造——AutowireAnnotationBeanPostProcessor#determineCandidateConstructors二、autowireConstructor 方法源码解析三、总结 阅读此需阅读下面这些博客先【Spring源码分析】Bean的元数据和一些Spring的工具【Spring源码分析】BeanFactory系…

【Java程序设计】【C00207】基于(JavaWeb+SSM)的宠物领养管理系统(论文+PPT)

基于&#xff08;JavaWebSSM&#xff09;的宠物领养管理系统&#xff08;论文PPT&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于ssm的宠物领养系统 本系统分为前台系统、管理员、收养者和寄养者4个功能模块。 前台系统&#xff1a;游客打开系统…

机器学习入门-----sklearn

机器学习基础了解 概念 机器学习是人工智能的一个实现途径 深度学习是机器学习的一个方法发展而来 定义:从数据中自动分析获得模型,并利用模型对特征数据【数据集:特征值+目标值构成】进行预测 算法 数据集的目标值是类别的话叫做分类问题;目标值是连续的数值的话叫做回…

FullStack之Django(1)开发环境配置

FullStack之Django(1)开发环境配置 author: Once Day date&#xff1a;2022年2月11日/2024年1月27日 漫漫长路&#xff0c;才刚刚开始… 全系列文档请查看专栏: FullStack开发_Once_day的博客-CSDN博客Django开发_Once_day的博客-CSDN博客 具体参考文档: The web framewor…

Docker中配置MySql环境

目录 一、简单安装 1. 首先从Docker Hub中拉取镜像 2. 启动尝试创建MySQL容器&#xff0c;并设置挂载卷。 3. 查看mysql8这个容器是否启动成功 4. 如果已经成功启动&#xff0c;进入容器中简单测试 4.1 进入容器 4.2 登录mysql中 4.3 进行简单添加查找测试 二、主从复…

C++函数分文件编写之VScode版

VScode实现函数的分文件编写 1.下载插件创建项目2.分文件编写内容3.修改主函数文件名 我在分享内容时经常用的软件是VScode&#xff0c;相信有些内存敏感或需要VScode便利性的小伙伴也是更愿意使用VScode。那么接下来我们就盘一盘怎样使用VScode实现分文件编写。 1.下载插件创建…

20240202在WIN10下使用fast whisper缺少cudnn_ops_infer64_8.dll

20240202在WIN10下使用fast whisper缺少cudnn_ops_infer64_8.dll 2024/2/2 10:48 https://blog.csdn.net/feinifi/article/details/132548556 Could not locate cudnn_ops_infer64_8.dll. Please make sure it is in your library path!解决办法 安装cuDNN c:\faster-whisper-…

用HTML5 + JavaScript实现下雪效果

用HTML5 JavaScript实现下雪效果 下面是用HTML5 JavaScript实现下雪效果示例&#xff0c;展示了如何使用 HTML5 的 <canvas> 元素以及 JavaScript 来创建下雪效果。效果如下&#xff1a; 源码如下&#xff1a; <!DOCTYPE html> <html lang"en">…

【Vue3】源码探索之旅:compiler-core之parseChildren函数(二)

简言 parseChildren函数是在baseParse函数中作为createRoot函数的子节点参数传入的&#xff0c;今天来探索下parseChildren函数。 parseChildren在 compiler-core/src/parse.ts文件内。 parseChildren 这个函数就是用来解析模板字符串内容的 &#xff0c;里面有个while循环…

vue全家桶之状态管理Vuex

一、认识应用状态管理 1.什么是状态管理 在开发中&#xff0c;我们会的应用程序需要处理各种各样的数据&#xff0c;这些数据需要保存在我们应用程序中的某一个位置&#xff0c;对于这些数据的管理我们就称之为是 状态管理。 在前面我们是如何管理自己的状态呢&#xff1f; …

HiSilicon352 android9.0 开机视频调试分析

一&#xff0c;开机视频概念 开机广告是在系统开机后实现播放视频功能。 海思Android解决方案在原生Android基础上&#xff0c;增加了开机视频模块&#xff0c;可在开机过程中播放视频文件&#xff0c;使用户更好的体验系统开机过程。 二&#xff0c;模块结构 1. 海思自研开机…

【Docker篇】Linux安装Docker、docker安装mysql、redis、rabbitmq

1.Linux安装docker 官方帮助文档&#xff1a;Install Docker Engine on CentOS | Docker Docs 1.1安装命令 # 1. 卸载之前的dockersudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate…

认识 SYN Flood 攻击

文章目录 1.什么是 SYN Flood 攻击&#xff1f;2.半连接与全连接队列3.如何防范 SYN Flood 攻击&#xff1f;增大半连接队列开启 SYN Cookie减少 SYNACK 重传次数 参考文献 1.什么是 SYN Flood 攻击&#xff1f; SYN Flood 是互联网上最原始、最经典的 DDoS&#xff08;Distri…

dvwa,xss反射型lowmedium

xss&#xff0c;反射型&#xff0c;low&&medium low发现xss本地搭建实操 medium作为初学者的我第一次接触比较浅的绕过思路high low 发现xss 本关无过滤 <script>alert(/xss/)</script> //或 <script>confirm(/xss/)</script> //或 <scr…

2024数学建模美赛F题思路代码分享

非法的野生动物贸易会对我们的环境产生负面影响&#xff0c;并威胁到全球的生物多样性。据估 计&#xff0c;它每年涉及高达265亿美元&#xff0c;被认为是全球第四大非法交易。[1]你将开发一个由数 据驱动的5年项目&#xff0c;旨在显著减少非法野生动物贸易。你的目标是说服一…

【24美赛思路已出】2024年美赛A~F题解题思路已出 | 无偿自提

A题&#xff1a;资源可用性和性别比例 问题一&#xff1a; 涉及当灯鱼种群的性别比例发生变化时&#xff0c;对更大的生态系统产生的影响。为了分析这个问题&#xff0c;可以采用以下的数学建模思路&#xff1a;建立灯鱼种群模型&#xff1a; 首先&#xff0c;建立一个灯鱼种群…

C语言第十六弹---操作符(下)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 操作符 1、下标访问[]、函数调用() 1.1、[ ] 下标引用操作符 1.2、函数调用操作符 2、结构成员访问操作符 2.1、结构体 2.1.1、结构的声明 2.1.2、结构体变…

计算机网络第4章(网络层)

4.1、网络层概述 简介 网络层的主要任务是实现网络互连&#xff0c;进而实现数据包在各网络之间的传输 这些异构型网络N1~N7如果只是需要各自内部通信&#xff0c;他们只要实现各自的物理层和数据链路层即可 但是如果要将这些异构型网络互连起来&#xff0c;形成一个更大的互…