当前位置: 首页 > 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方式…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...