刷题日记-139. 单词拆分

这是一道动态规划题目,要求判断给出的字符串s能否被wordDict字符串列表中的字符串组成。

这段代码是一个解决单词拆分问题的函数 `wordBreak`,其作用是判断字符串 `s` 是否可以被拆分为由字典 `wordDict` 中的单词组成。

我们要通过构建一个布尔值的向量 `dp`,来判断字符串 `s` 是否可以被拆分为字典中的单词。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string>();
        for(auto word:wordDict){
            wordDictSet.insert(word);
        }

`wordBreak` 函数接受两个参数:一个字符串 `s` 和一个字符串向量 `wordDict`。
在函数内部,先创建一个空的 `unordered_set<string>` 类型的变量 `wordDictSet`。
使用范围循环遍历 `wordDict`,将其中的每个单词插入到 `wordDictSet` 中(把字典内容插入wordDictSet中是为了后面使用wordDictSet.find查找单词)

    auto dp = vector<bool>(s.size()+1);
    dp[0]=true;
    for(int i=1;i<=s.size();i++){

创建一个存储布尔值的向量 `dp`,大小为 `s.size()+1`。
将 `dp[0]` 设置为 `true`,即空字符串可以被拆分为字典中的单词(即使用0个字典单词)。

        for(int j=0;j<i;j++){
            if(dp[j]&&wordDictSet.find(s.substr(j,i-j))!=wordDictSet.end()){
                dp[i]=true;
                break;
            }
        }
     }

使用两个循环嵌套,外层循环遍历 `s` 的每个字符位置 `i`。
内层循环遍历从 0 到 `i` 的所有可能的拆分点 `j`。
在每个拆分点 `j` 处,检查子字符串 `s.substr(j, i-j)` 是否存在于 `wordDictSet` 中
如果找到了一个拆分点 `j`,且 `dp[j]` 为 `true`,表示从起始位置到 `j` 的子字符串可以被拆分为字典中的单词,那么将 `dp[i]` 设置为 `true`。
最后,如果 `dp[s.size()]` 为 `true`,表示整个字符串 `s` 可以被拆分为字典中的单词,返回 `true`;否则返回 `false`。

注意:

在这段代码中,wordDictSet.find(s.substr(j,i-j)) 返回的是一个迭代器,而不是直接的结果值。如果找到了对应的子字符串,则返回指向该子字符串的迭代器;如果没有找到,则返回 wordDictSet.end(),表示迭代器指向字典集合的末尾。

所以在这段代码中,应该使用 wordDictSet.find(s.substr(j,i-j)) != wordDictSet.end() 来判断是否找到了对应的子字符串,而不是与0或-1进行比较。

        return dp[s.size()];
    }
};

函数最后返回 `dp[s.size()]`,表示整个字符串 `s` 是否可以被拆分为字典中的单词。


上面是c++写法

接下来再用JavaScript实现:

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    const n=s.length;
    const dp=new Array(n+1).fill(false);
    dp[0]=true;
    for(var i=1;i<=n;i++){
        for(var j=0;j<i;j++){
            if(dp[j]&&wordDict.indexOf(s.substring(j,i))!==-1){
                dp[i]=true;
                break;
            }
        }
    }
    return dp[n];
}

c++和JavaScript库的使用上很多地方有所不同

比如 变量的创建(注意类型),查找字符串,分割字符串等,注意区分。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Godot4自学手册】第一节配置Godot运行环境

各位同学大家好&#xff01;我是相信神话&#xff0c;从今天开始&#xff0c;我开始自学2D游戏开发&#xff0c;用到的是Godot4。我准备用视频记录整个开发过程&#xff0c;为自学2D开发的同学趟趟路。让我们开始吧。 首先介绍一下Godot是什么东西&#xff0c;在2D游戏开发中是…

DolphinDB学习(0):DolphinDB基本概述

DolphinDB的学习难度不小&#xff0c;主要是写法比较多&#xff0c;官方示例是一次性给一大堆代码&#xff0c;在没有成体系的学习基础的前提下&#xff0c;总有种力不从心的感觉&#xff0c;所以博主汇总这一个系列的文章&#xff0c;尝试从最简单的基础常规操作开始&#xff…

springboot113健身房管理系统

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的健身房管理系统 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取…

力扣刷MySQL-第七弹(详细讲解)

&#x1f389;欢迎您来到我的MySQL基础复习专栏 ☆* o(≧▽≦)o *☆哈喽~我是小小恶斯法克&#x1f379; ✨博客主页&#xff1a;小小恶斯法克的博客 &#x1f388;该系列文章专栏&#xff1a;力扣刷题讲解-MySQL &#x1f379;文章作者技术和水平很有限&#xff0c;如果文中出…

一文详解 Berachain 测试网:全面介绍与教程,bitget wallet教程

什么是Berachain&#xff1f; Berachain&#xff08;web3.bitget.com/zh-CN/assets/berachain-wallet&#xff09;是一种尖端区块链技术&#xff0c;使用 Cosmos SDK 构建的 Layer-1&#xff0c;兼容以太坊虚拟机&#xff08;EVM&#xff09;。它基于一种独特的概念&#xff0c…

Summerize for Bioinformatics with ChatGPT

目录 Basic Introduction Historical Events Bioinformatics vs. Computational Biology Levels of Bioinfo & CompBio Molecular Biology Primer Homework 1 A brief Introduction to DNA & RNA A brief Introduction to Protein Sequencing Technologies S…

解决git在使用代理时进行HTTPS操作时的无法连接github的解决办法

问题如下&#xff1a; 在使用git clone 无法连接github的443端口。 解决问题&#xff1a; 首先查看自己的代理服务器使用的端口号&#xff08;我这里的端口号是7890。&#xff09;使用指令 git config --global https.proxy 127.0.0.1:7890这条命令是在配置 Git 使用代理服务…

【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

一、归并排序 归并排序是一种经典的排序算法&#xff0c;它使用了分治法的思想。下面是归并排序的算法思想&#xff1a; 递归地将数组划分成较小的子数组&#xff0c;直到每个子数组的长度为1或者0。将相邻的子数组合并&#xff0c;形成更大的已排序的数组&#xff0c;直到最…

【Android12】Android Framework系列---Adb和PMS安装apk源码流程

Adb和PMS安装apk源码流程 adb install命令 通过adb install命令可以将apk安装到Android系统&#xff08;注意&#xff1a;特定类型的apk&#xff0c;比如persist类型是无法通过adb安装的&#xff09; 下述命令中adb解析install命令&#xff0c;并调用Android PackageManagerS…

KAGGLE · GETTING STARTED CODE COMPETITION 图像风格迁移 示例代码阅读

本博文阅读的代码来自于I’m Something of a Painter Myself | Kaggle倾情推荐&#xff1a; Monet CycleGAN Tutorial | Kaggle 数据集说明 I’m Something of a Painter Myself | Kaggle Files monet_jpg - 300 Monet paintings sized 256x256 in JPEG formatmonet_tfrec -…

go语言(十一)----面向对象继承

一、面向对象继承 写一个父类 package mainimport "fmt"type Human struct {name stringsex string }func (this *Human) Eat() {fmt.Println("Human.Eat()...") }func (this *Human) Walk() {fmt.Println("Human.Walk()...") }func main() {h…

B(l)utter:一款针对Flutter移动端应用程序的逆向工程分析工具

关于B(l)utter B(l)utter是一款针对Flutter移动端应用程序的逆向工程分析工具&#xff0c;当前版本的B(l)utter仅支持Android libapp.so&#xff08;ARM64&#xff09;&#xff0c;可以帮助广大研究人员对基于Flutter开发的移动端应用程序进行逆向工程分析。 环境搭建 该应用…

dpdk网络转发环境的搭建

文章目录 前言ip命令的使用配置dpdk-basicfwd需要的网络结构测试dpdk-basicfwddpdk-basicfwd代码分析附录basicfwd在tcp转发时的失败抓包信息DPDK的相关设置 前言 上手dpdk有两难。其一为环境搭建。被绑定之后的网卡没有IP&#xff0c;我如何给它发送数据呢&#xff1f;当然&a…

全国各省市上市公司数量数据,Shp、excel格式,含上市企业数量、行政区划中心点位经纬度等字段

基本信息. 数据名称: 全国各省市上市公司数量数据 数据格式: Shp、excel 数据时间: 2023年1月 数据几何类型: 面 数据坐标系: WGS84 数据来源&#xff1a;网络公开数据 数据字段&#xff1a; 序号字段名称字段说明1province省份名称2provin_dm省份代码3city城市名…

学习CANopen --- [12] Abort报文

当我们使用SDO进行读写操作时&#xff0c;有时device会返回abort报文&#xff0c;意味着本次SDO读写失败。本文使用例子来讲解Abort报文&#xff0c;以及如何解读失败原因。 一 Device例子 下面是device的python代码&#xff0c;文件名叫device.py&#xff0c;device的CANopen…

02. VBA从入门到精通——基础语法

数据类型 常用数据类型 Integer&#xff1a;整数&#xff0c;-32,768到32,767之间的整数 Long&#xff1a;较长长整数&#xff0c;-2,147,483,648到2,147,483,647之间的整数 Single:浮点数&#xff0c;它可以存储大约&#xff1a;6到7位小数的精度。 Double&#xff1a;较长浮…

免费的WordPress插件大全

在当今数字化的时代&#xff0c;拥有一个强大的在线存在变得至关重要。而对于使用WordPress建站的用户来说&#xff0c;插件是提高网站功能的关键。在这篇文章中&#xff0c;我们将为您推荐三款免费的WordPress插件&#xff0c;它们不仅是147SEO软件中的佼佼者&#xff0c;而且…

【Leetcode】接雨水(双指针、单调栈)

目录 &#x1f4a1;题目描述 &#x1f4a1;双指针解法 &#x1f4a1;单调栈解法 &#x1f4a1;题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 提示&#xff1a; n height.length1 < n…

this.$set的用法

作用&#xff1a; 在data里面绑定的数据具有响应式的效果,也就是我们说的V-Model 数据更新视图,视图也能更新数据&#xff0c;如果不是data里面的数据如何添加响应式呢&#xff1f; this.$Set这个方法能够实现 用法&#xff1a; this.$Set(要添加的对象,要添加的属性’,要添…

为什么C++17要引入std::string_view?

目录 1.引言 2.原理分析 2.1.结构 2.2.构造函数 2.3.成员函数 2.4.std::string_view字面量 3.实例 3.1.std::string_view和std::string的运算符操作 3.2.查找函数使用 3.3.std::string_view和临时字符串 4.总结 1.引言 在C/C日常编程中&#xff0c;我们常进行数据的…
最新文章