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

力扣139.单词拆分

 思路:动态规划,设dp[]记录当前字符能不能通过字典里的单词到达,双层循环,外层循环遍历字符串每一个字符,内层遍历当前i字符之前的所有以i字符结尾的子串

例如字符串:leetcode

i遍历到了t

那么内层循环就会遍历:leet、eet、et、t

然后判断这些子串中有没有与字典里的单词匹配,若匹配且当前dp[j]为真,则dp[i]为真

判断dp[j] 是因为若dp[j]为真,则代表j字符可以到达,那么当前字符子串以j为起始并且字典里存在此子串,所以当前子串的结尾处也可以到达(dp[i] = true)

dp[0] 赋初值true,因为若子串起始字符为第一个字符,那么从第一个字符出发的子串当然是可以的

最后判断dp[]最后一个位置是否为真,若为真则说明此字符串可以通过字典里的单词拼凑到达最后一个字符

一开始的笨办法,虽然笨且慢,不过可能更便于理解:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.size();auto dp = vector<bool> (len + 1);    dp[0] = true;    //dp[0]赋值for(int i = 1; i <= len; i++){     //外层循环遍历字符串int sw = true;    //开关,若内层循环确定当前字符可到达则进行下一个字符for(int j = 0; j < i && sw; j++){    //内层循环遍历i字符前每一个以i字符结尾的子串for(auto word:wordDict){    //在字典里面找有没有此子串if(dp[j] && (word.compare(s.substr(j, i - j)) == 0)){    dp[i] = true;    //如果子串存在可到达则i字符后一个字符也可到达sw = false;    //如果当前字符可到达则无需继续遍历子串}}}}return dp[len];}
};

加入unordered_set之后快了很多

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int len = s.size();auto dp = vector<bool> (len + 1);dp[0] = true;auto wordset = unordered_set <string> ();for(auto word : wordDict){wordset.insert(word);}for(int i = 1; i <= len; i++){for(int j = 0; j < i; j++){if(dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()){dp[i] = true;break;}}}return dp[len];}
};

思路不变,unordered_set就是一个key为值的字典,并且unordered_set中find()若找不到对应元素,会返回.end()

相关文章:

力扣139.单词拆分

思路&#xff1a;动态规划&#xff0c;设dp[]记录当前字符能不能通过字典里的单词到达&#xff0c;双层循环&#xff0c;外层循环遍历字符串每一个字符&#xff0c;内层遍历当前i字符之前的所有以i字符结尾的子串 例如字符串&#xff1a;leetcode i遍历到了t 那么内层循环就…...

Docker 镜像命令总汇

目录 1、查看镜像列表 2、搜索镜像 3、拉取镜像 4、删除镜像 5、显示镜像详细信息 6、显示镜像历史 7、导出镜像 8、导入镜像 9、清理未使用的镜像 10、强制删除镜像 1、查看镜像列表 docker images 这个命令列出了你系统中的所有 Docker 镜像&#xff0c;包括镜像名…...

客户服务:助力企业抵御经济衰退的关键要素与策略

目前经济仍悬而未决是否陷入衰退。当前情况下&#xff0c;尽管通胀率高企&#xff0c;消费者支出良好&#xff0c;就业率也在上升&#xff0c;表明就业市场强劲。然而&#xff0c;有人认为衰退可能会在2024年第一季度发生。经济环境的不确定性可能会让人望而却步&#xff0c;但…...

第八周:AIPM面试准备

以下为从开始准备转行到拿到offer期间每天需要准备的10个面试题目以及相关知识补充&#xff01;来源广泛&#xff0c;从各个地方收集&#xff0c;只提供题目&#xff0c;我自己的尝试回答也会陆续放在我的喜马拉雅&#xff0c;基于我粗浅的认知&#xff0c;分享我粗浅的作答思路…...

阿里云2核2G3M服务器能放几个网站?有限制吗?

阿里云2核2g3m服务器可以放几个网站&#xff1f;12个网站&#xff0c;阿里云服务器网的2核2G服务器上安装了12个网站&#xff0c;甚至还可以更多&#xff0c;具体放几个网站取决于网站的访客数量&#xff0c;像阿里云服务器网aliyunfuwuqi.com小编的网站日访问量都很少&#xf…...

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机本身的数据保存(CustomData)功能(C#)

Baumer工业相机堡盟工业相机如何通过NEOAPI SDK设置相机本身的数据保存&#xff08;CustomData&#xff09;功能&#xff08;C#&#xff09; Baumer工业相机Baumer工业相机的数据保存&#xff08;CustomData&#xff09;功能的技术背景CameraExplorer如何使用图像剪切&#xff…...

从零开始配置kali2023环境:镜像保存和导入

对原始的镜像做了一些改动&#xff0c;然后把当前容器状态打包为新的镜像&#xff0c;这样以后可以部署到其他地方了&#xff0c;而不用再安装软件等改动等等 1.查看容器id ┌──(holyeyes㉿kali2023)-[~] └─$ sudo docker ps ┌──(holyeyes㉿kali2023)-[~] └─$ s…...

Transformer梳理与总结

其实transformer的成功也是源于对注意力机制的应用&#xff0c;其本质上还是可以归因于注意力机制&#xff0c;首先我们先来了解一下什么是注意力机制。在注意力机制的背景下&#xff0c;自主性提示被称为查询&#xff08;query&#xff09;,给定任何查询&#xff0c;注意力机制…...

php之 校验多个时间段是否重复

参考网址 https://www.kancloud.cn/xiaobaoxuetp/mywork/3069416 https://segmentfault.com/a/1190000020487996 PHP判断多个时间段是否存在跨天或重复叠加的场景 /*** PHP计算两个时间段是否有交集&#xff08;边界重叠不算&#xff09;** param string $beginTime1 开始时间…...

atoi函数的模拟实现

这里强力推荐一篇文章 http://t.csdnimg.cn/kWuAm 详细解析了atoi函数以及其模拟实现&#xff0c;我这里就不说了。 这里作者先把自己模拟的代码给大家看一下。 int add(char* arr) {char* arr2 arr;while (*arr!-48){arr;}arr--;int sum 0;int n 0;while (arr ! (arr2-…...

编程笔记 html5cssjs 009 HTML链接

编程笔记 html5&css&js 009 HTML链接 一、HTML 链接二、文本链接三、图片链接四、HTML 链接- id 属性五、锚点链接六、HTML 链接 - target 属性七、属性downloadhrefpingreferrerpolicyreltargettype 八、操作小结 网页有了链接&#xff0c;就可根据需要进行跳转。纸质…...

Vue实现导出Excel表格,提示“文件已损坏,无法打开”的解决方法

一、vue实现导出excel 1、前端实现 xlsx是一个用于读取、解析和写入Excel文件的JavaScript库。它提供了一系列的API来处理Excel文件。使用该库&#xff0c;你可以将数据转换为Excel文件并下载到本地。这种方法适用于在前端直接生成Excel文件的场景。 安装xlsx依赖 npm inst…...

分发糖果,Java经典算法编程实战。

&#x1f3c6;作者简介&#xff0c;普修罗双战士&#xff0c;一直追求不断学习和成长&#xff0c;在技术的道路上持续探索和实践。 &#x1f3c6;多年互联网行业从业经验&#xff0c;历任核心研发工程师&#xff0c;项目技术负责人。 &#x1f389;欢迎 &#x1f44d;点赞✍评论…...

鸿蒙原生应用再添新丁!中国移动 入局鸿蒙

鸿蒙原生应用再添新丁&#xff01;中国移动 入局鸿蒙 来自 HarmonyOS 微博1月2日消息&#xff0c;#中国移动APP启动鸿蒙原生应用开发#&#xff0c;拥有超3亿用户的中国移动APP宣布&#xff0c;正式基于HarmonyOS NEXT启动#鸿蒙原生应用#及元服务开发。#HarmonyOS#系统的分布式…...

一个人能不能快速搭建一套微服务环境

一、背景 大型软件系统的开发现在往往需要多人的协助&#xff0c;特别是前后端分离的情况下下&#xff0c;分工越来越细&#xff0c;那么一个人是否也能快速搭建一套微服务系统呢&#xff1f; 答案是能的。看我是怎么操作的吧。 二、搭建过程 1、首先需要一套逆向代码生成工…...

计算机毕业设计------经贸车协小程序

项目介绍 本项目分为三种用户类型&#xff0c;分别是租赁者&#xff0c;车主&#xff0c;管理员用户&#xff1b; 管理员用户包含以下功能&#xff1a; 管理员登录,个人中心,租赁者管理,车主管理,赛事活动管理,车类别管理,租车管理,租车订单管理,车辆出售管理,购买订单管理,…...

数据结构OJ实验11-拓扑排序与最短路径

A. DS图—图的最短路径&#xff08;无框架&#xff09; 题目描述 给出一个图的邻接矩阵&#xff0c;输入顶点v&#xff0c;用迪杰斯特拉算法求顶点v到其它顶点的最短路径。 输入 第一行输入t&#xff0c;表示有t个测试实例 第二行输入顶点数n和n个顶点信息 第三行起&…...

你的第一个JavaScript程序

JavaScript&#xff0c;即JS&#xff0c;JavaScript是一种具有函数优先的轻量级&#xff0c;解释型或即时编译型的编程语言。虽然它是作为开发Web页面的脚本语言而出名&#xff0c;但是它也被用到了很多非浏览器环境中&#xff0c;JavaScript基于原型编程、多范式的动态脚本语言…...

CMake入门教程【基础篇】列表操作(list)

文章目录 1. 定义列表2. 获取列表长度3. 获取列表元素4. 追加元素到列表末尾5. 插入元素到指定位置6. 移除指定位置的元素7. 移除指定值的元素8. 替换指定位置的元素9. 迭代列表元素 #mermaid-svg-IAjFPWI6IXEGYmuU {font-family:"trebuchet ms",verdana,arial,sans-…...

普中STM32-PZ6806L开发板(HAL库函数实现-读取内部温度)

简介 主芯片STM32F103ZET6&#xff0c;读取内部温度其他知识 内部温度所在ADC通道 温度计算公式 V25跟Avg_Slope值 参考文档 stm32f103ze.pdf 电压计算公式 Vout Vref * (D / 2^n) 其中Vref代表参考电压&#xff0c; n为ADC的位数&#xff0c; D为ADC输入的数字信号。 实现…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

yaml读取写入常见错误 (‘cannot represent an object‘, 117)

错误一&#xff1a;yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因&#xff0c;后面把yaml.safe_dump直接替换成yaml.dump&#xff0c;确实能保存&#xff0c;但出现乱码&#xff1a; 放弃yaml.dump&#xff0c;又切…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

基于Java项目的Karate API测试

Karate 实现了可以只编写Feature 文件进行测试,但是对于熟悉Java语言的开发或是测试人员,可以通过编程方式集成 Karate 丰富的自动化和数据断言功能。 本篇快速介绍在Java Maven项目中编写和运行测试的示例。 创建Maven项目 最简单的创建项目的方式就是创建一个目录,里面…...