(※)力扣刷题-字符串-实现 strStr()(KMP算法)

news/2024/3/4 8:52:23

28 实现 strStr()

实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1
说明: **当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 对于本题而言,当 needle 是空字符串时我们应当返回 0 **。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

思路

首先是模式串匹配问题,需要先在hatstack(文本串)中找到needle子串(模式串),然后再去考虑求这个索引。第一个问题就涉及到KMP算法。KMP的经典思想就是:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。
以下代码随想录文字详细说明了KMP算法:
https://www.programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E6%80%9D%E8%B7%AF

解法一-前缀表(减一)

class Solution(object):# 第一步 首先要求next数组def getNext(self, next, s): # s表示模式串# 初始化j = -1next[0] = jfor i in range(1, len(s)): # 注意i从1开始 因为要比较 i 和 j是否相同# 前后缀不相同 while j>=0 and s[i]!=s[j+1]:j = next[j] # j回退# 前后缀相同if s[i]==s[j+1]:j += 1 # i和j都加1next[i] = j# 第二步 求下标索引def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""if not needle:return 0next = [0]*len(needle) # 初始化nextself.getNext(next, needle)j = -1for i in range(len(haystack)):while j >= 0 and haystack[i]!=needle[j+1]: # j+1是因为j初始值为-1j = next[j] # next数组起作用了 找下一个匹配的位置if haystack[i]==needle[j+1]: # 匹配到字符相同j += 1# 判断在文本串里出现了模式串if j == len(needle) - 1:return i - len(needle) + 1 # 返回索引return -1

暴力法

class Solution(object):def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""m, n = len(haystack), len(needle)for i in range(m):if haystack[i:i+n] == needle:return ireturn -1   

使用index(写算法题不推荐)

class Solution:def strStr(self, haystack: str, needle: str) -> int:try:return haystack.index(needle)except ValueError:return -1

使用find(写算法题不推荐)

class Solution:def strStr(self, haystack: str, needle: str) -> int:return haystack.find(needle)

http://www.ppmy.cn/news/1151648.html

相关文章

虚拟现实VR技术在医疗行业的应用介绍

虚拟现实 (VR) 虽然经常与游戏联系在一起,但不可否认,未来科技少不了虚拟现实,其应用可以彻底改变许多行业。在医疗领域,无数人正在探索 VR 可以帮助患者和医疗从业者实现更好的治疗结果治疗方式,比如在手术、疼痛管理…

Golang 实现接口和继承

小猴子继承了老猴子,这样老猴子拥有的能力包括字段,方法就会自动的被老猴子继承。 小猴子不需要做任何处理就可以拿到老猴子的字段和它的方法,因为是继承关系。 但是小猴子还会其他的技能,比如还会像小鸟一样飞翔,希…

electron 升级 v22 遇到问题

Electron 漏洞 https://mp.weixin.qq.com/s/5LpSJb_5uV8EIDOl3fz9Tw 由于 23以上不在支持win 7 8 8.1 所以我选择安装 v22.3.24 electron 22.3.24 node-sass 6.0.1 sass-loader 10.4.1 对应的版本 npm i node-sass6.0.1 --sass_binary_sitehttps://npm.taobao.org/mirrors…

web前端面试-- 在 JavaScript 中 bind , apply 和 call 的区别

本人是一个web前端开发工程师,主要是vue框架,整理了一些面试题,今后也会一直更新,有好题目的同学欢迎评论区分享 ;-) web面试题专栏:点击此处 在 JavaScript 中, bind , apply 和 c…

Spring Boot的循环依赖问题

目录 1.循环依赖的概念 2.解决循环依赖的方法 1.构造器方法注入: 2.Lazy注解 3.DependsOn注解 1.循环依赖的概念 两个或多个bean之间互相依赖,形成循环,此时,Spring容器无法确定先实例化哪个bean,导致循环依赖的…

分权分域有啥内容?

目前的系统有什么问题? 现在我们的系统越来越庞大,可是每一个人进来的查看到的内容完全一样,没有办法灵活的根据不同用户展示不同的数据 例如我们有一个系统,期望不同权限的用户可以看到不同类型的页面,同一个页面不…

IIS 解析漏洞复现

文章目录 IIS 解析漏洞复现1. 漏洞描述2. 漏洞复现3. 漏洞原因4. 安全加固5. 安全防护 IIS 解析漏洞复现 1. 漏洞描述 说明内容漏洞编号漏洞名称IIS 解析漏洞漏洞评级高危影响范围IIS 6.0及以前版本IIS 7.0IIS 7.5漏洞描述IIS 解析漏洞是指在 IIS 服务器上存在的安全漏洞&…

vue-插件

插件 插件通常用来为 Vue 添加全局功能。插件的功能范围没有严格的限制。 通过全局方法 Vue.use() 使用插件。它需要在你调用 new Vue() 启动应用之前完成 // 调用 MyPlugin.install(Vue) Vue.use(MyPlugin)new Vue({// ...组件选项 })本质:包含install方法的一个…

3D 生成重建007-Fantasia3D和Magic3d两阶段玩转文生3D

3D生成重建3D 生成重建007-Fantasia3D和magic3d 文章目录 0 论文工作1 论文方法1.1 magic3d1.2 Fantasia3D 2 效果2.1 magic3d2.2 fantasia3d 0 论文工作 两篇论文都是两阶段法进行文生3d,其中fantasia3D主要对形状和外表进行解耦,然后先对geometry进行…

Ant Design of React组件引用及路由跳转

Ant Design of React 学习笔记(2) Ant Design of React组件引用及路由跳转,接着笔记(1)继续 这里我们主要3点:1.使用Ant的组件;2,如何引用页面组件;3,路由导航跳转 这是我的目录结…

TypeScript React(上)

目录 扩展学习资料 TypeScript设计原则 TypeScript基础 语法基础 变量声明 JavaScript声明变量 TypeScript声明变量 示例 接口 (标准类型-Interface) 类型别名-Type 接口 VS 类型别名 类型断言:欺骗TS&#xff0c;肯定数据符合结构 泛型、<大写字母> 扩展学习…

c语言之strcmp函数使用和实现

文章目录 前言一、strcmp函数使用二、实现方法 前言 c语言中常用的字符串处理函数strcmp总结。 一、strcmp函数使用 原型 int strcmp ( const char * str1, const char * str2 );strcmp比较两个字符串的大小&#xff0c;一个字符一个字符比较&#xff0c;按ASCII码比较 规定…

汽车RNC主动降噪算法DSP C程序实现

汽车RNC主动降噪算法C程序 是否需要申请加入数字音频系统研究开发交流答疑群(课题组)?可加我微信hezkz17, 本群提供音频技术答疑服务,车载

python 之xml 使用原生xml.dom

一、xml操作 使用xml进行创建<Placemark id"placemark_id"><name>模型</name><Location><longitude>121.6097139799135</longitude></Location> </Placemark>from xml.dom import minidom# 创建一个新的XML文档 do…

pytorch中的池化函数

PyTorch 提供了多种池化函数&#xff0c;用于对输入数据进行不同类型的池化操作。以下是一些常用的 PyTorch 池化函数&#xff1a; 平均池化&#xff08;Average Pooling&#xff09;: nn.AvgPool1d: 一维平均池化。nn.AvgPool2d: 二维平均池化。nn.AvgPool3d: 三维平均池化。 …

Linux友人帐之系统管理与虚拟机相关

一、虚拟机相关操作 1.1虚拟机克隆 虚拟机克隆是指将一个已经安装好的虚拟机复制出一个或多个完全相同的副本&#xff0c;包括虚拟机的配置、操作系统、应用程序等&#xff0c;从而节省安装和配置的时间和资源。 虚拟机克隆的主要用途有&#xff1a; 创建多个相同或相似的虚拟…

走进Spark

什么是Spark 是一个基于内存的&#xff0c;用于大规模数据处理&#xff08;离线计算、实时计算、快速查询&#xff08;交互式查询&#xff09;&#xff09;的统一分析引擎&#xff0c;因为是基于内存的所以可以更快的完成任务 离线计算:离线计算一般存储在HDFS中使用MapReduce或…

电商数据接口平台1688阿里巴巴获得搜索词推荐获取商品详情数据

1688.item_search_suggest-获得搜索词推荐 公共参数 请求地址: 注册请求接入调用key 名称类型必须描述keyString是调用key&#xff08;必须以GET方式拼接在URL中&#xff09;secretString是调用密钥api_nameString是API接口名称&#xff08;包括在请求地址中&#xff09;[ite…

uni-app:本地缓存的使用

uni-app 提供了多种方法用于本地缓存的操作。下面是一些常用的 uni-app 本地缓存方法&#xff1a; uni.setStorageSync(key, data): 同步方式将数据存储到本地缓存中&#xff0c;可以使用对应的 key 来获取该数据。 uni.setStorage({key, data}): 异步方式将数据存储到本地缓存…

【小巧玲珑】文件太大,怎么办?分卷压缩技术了解下,这才是压缩技术

【小巧玲珑】文件太大&#xff0c;怎么办&#xff1f;分卷压缩技术了解下&#xff0c;这才是压缩技术 1、痛点2、场景重现2.1 jar包2.1 ZIP压缩 3、压缩步骤3.1 新建压缩文件3.2 压缩结果 4、解压步骤5、效果6、jar压缩算法 1、痛点 通过浏览器客户端访问云服务&#xff0c;文…
最新文章