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

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

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)

相关文章:

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

28 实现 strStr() 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。 示例 1: 输入: haystack “hello”, needle “ll” 输出: 2 示例…...

Redis 集群 Redis 事务 Redis 流水线 Redis 发布订阅 Redis Lua脚本操作

Redis 集群 & Redis 事务 & Redis 流水线 & Redis 发布订阅 Redis 集群linux安装redis主从配置查看当前实例主从信息 Redis Sentinelsentinel Redis Cluster Redis 事务Redis 流水线Redis 发布订阅Redis Lua脚本操作 Redis 集群 linux安装redis 下载安装包&#…...

【算法与数据结构】--常见数据结构--栈和队列

一、栈 栈(Stack) 是一种基本的数据结构,具有后进先出(LIFO)的特性,类似于现实生活中的一叠盘子。栈用于存储一组元素,但只允许在栈顶进行插入(入栈)和删除(…...

Linux shell编程学习笔记11:关系运算

Linux Shell 脚本编程和其他编程语言一样,支持算数、关系、布尔、字符串、文件测试等多种运算。前面几节我们研究了 Linux shell编程 中的 字符串运算 和 算术运算,今天我们来研究 Linux shell编程中的的关系运算。 一、关系运算符功能说明 运算符说明…...

JS标准库

学习一门编程语言不仅是掌握其语法。同等重要的是学习其标准库,从而熟练掌握语言本身提供的所有工具。 1 定型数组 js常规数组与C和Java等较低级语言的数组类型还是有很大区别。ES6新增了定型数组,与这些语言的低级数组非常接近。 定型数组严格来说并…...

Android 12.0 hal层添加自定义hal模块功能实现

1. 前言 在12.0的系统rom定制化开发中,在 对hal模块进行开发时,需要通过添加自定义的hal模块来实现某些功能时,就需要添加hal模块的相关功能,接下来就来实现一个案例来供参考 接下来就来具体实现这个功能 2.hal层添加自定义hal模块功能实现的核心类 hardware\interfaces…...

如何理解vue声明式渲染

Vue.js中的声明式渲染是一种用来描述用户界面的方式,它强调“声明”应该如何渲染页面,而不需要关心底层的DOM操作。这与传统的命令式渲染方式,即手动控制DOM元素的创建、更新和销毁,形成了鲜明的对比。 理解Vue的声明式渲染的关键…...

【已解决】Vue全局引入scss 个别页面不生效 / 不自动引入全局样式

项目里配置了全局样式的引入,今天新建了 demo 页面去修改 element 的样式,发现全局的样式没有引入进来。 问题原因 在此页面 没有任何样式导致的 项目在编译的时候,会把 .vue 文件的样式抽离到单独的 css 文件中。 当该页面没有css代码的时…...

MySQL之双主双从读写分离

一个主机 Master1 用于处理所有写请求,它的从机 Slave1 和另一台主机 Master2 还有它的从 机 Slave2 负责所有读请求。当 Master1 主机宕机后, Master2 主机负责写请求, Master1 、 Master2 互为备机。架构图如下 : 准备 我们…...

使用eBPF加速阿里云服务网格ASM

背景 随着云原生应用架构的快速发展,微服务架构已经成为了构建现代应用的主要方式之一。而在微服务架构中,服务间的通信变得至关重要。为了实现弹性和可伸缩性,许多组织开始采用服务网格技术来管理服务之间的通信。 Istio作为目前最受欢迎的…...

大型数据集处理之道:深入了解Hadoop及MapReduce原理

在大数据时代,处理海量数据是一项巨大挑战。而Hadoop作为一个开源的分布式计算框架,以其强大的处理能力和可靠性而备受推崇。本文将介绍Hadoop及MapReduce原理,帮助您全面了解大型数据集处理的核心技术。 Hadoop简介 Hadoop是一个基于Google…...

LCR 095. 最长公共子序列(C语言+动态规划)

1. 题目 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符&#xff08…...

程序员不写注释:探讨与反思

一、为什么程序员不写注释 当程序员选择不写注释时,通常有一系列常见原因,这些原因可以影响他们的决策和行为。同时,这个决策可能会带来多方面的影响和后果。以下是详细阐述为什么程序员不写注释的常见原因以及这种决策可能导致的影响和后果…...

《论文阅读:Dataset Condensation with Distribution Matching》

点进去这篇文章的开源地址,才发现这篇文章和DC DSA居然是一个作者,数据浓缩写了三篇论文,第一篇梯度匹配,第二篇数据增强后梯度匹配,第三篇匹配数据分布。DC是匹配浓缩数据和原始数据训练一次后的梯度差,DS…...

免费chatGPT工具

发现很多人还是找不到好用的chatGPT工具,这里分享一个邮箱注册即可免费试用。 PromptsZone - 一体化人工智能平台使用 PromptsZone 与 ChatGPT、Claude、AI21 Labs、Google Bard 聊天,并使用 DALL-E、Stable Diffusion 和 Google Imagegen 创建图像&…...

数据分析基础:数据可视化+数据分析报告

数据分析是指通过对大量数据进行收集、整理、处理和分析,以发现其中的模式、趋势和关联,并从中提取有价值的信息和知识。 数据可视化和数据分析报告是数据分析过程中非常重要的两个环节,它们帮助将数据转化为易于理解和传达的形式&#xff0…...

settings.xml的文件配置大全

settings.xml 文件中最常配置的还是这几个标签 localRepository和mirrors settings.xml文件官方文档地址 <settings xmlns"http://maven.apache.org/SETTINGS/1.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"ht…...

极简c++(7)类的继承

为什么要用继承 子类不必复制父类的任何属性&#xff0c;已经继承下来了&#xff1b;易于维护与编写&#xff1b; 类的继承与派生 访问控制规则 一般只使用Public&#xff01; 构造函数的继承与析构函数的继承 构造函数不被继承&#xff01; 在创建子类对象的时候&…...

DOSBox和MASM汇编开发环境搭建

DOSBox和MASM汇编开发环境搭建 1 安装DOSBox2 安装MASM3 编译测试代码4 运行测试代码5 调试测试代码 本文属于《 X86指令基础系列教程》之一&#xff0c;欢迎查看其它文章。 1 安装DOSBox 下载DOSBox和MASM&#xff1a;https://download.csdn.net/download/u011832525/884180…...

047:mapboxGL本地上传shp文件,在map上解析显示图形

第047个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中本地上传shp文件,利用shapefile读取shp数据,并在地图上显示图形。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共117行)加载shapefile.js方式…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...