【力扣算法20】之 8. 找出字符串中第一个匹配项的下标 (python方向)

文章目录

  • 问题描述
    • 示例1
    • 示例2
    • 提示
  • 思路分析
  • 代码分析
  • 完整代码
  • 详细分析
  • 运行效果截图
    • 调用示例
    • 运行结果
  • 完结

问题描述

在这里插入图片描述

给你两个字符串 haystack needle ,请你在haystack字符串中找出needle字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是haystack的一部分,则返回 -1

在这里插入图片描述

示例1

输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

示例2

输入:haystack = “leetcode”, needle = “leeto”
输出:-1
解释:“leeto” 没有在 “leetcode” 中出现,所以返回 -1 。

提示

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

思路分析

在这里插入图片描述

在解决这个问题时,可以采用双指针的思路。首先,我们将两个指针分别指向 haystackneedle 的起始位置。然后,我们开始遍历 haystack 字符串,比较当前指针位置处的字符是否与 needle 字符串中的字符相同。如果相同,我们就继续比较下一个字符,直到完全匹配或者遍历完了 needle 字符串。

步骤如下:

  1. needle 是空字符串,则返回下标 0。
  2. 计算 haystackneedle 的长度,分别记为 nm
  3. haystack 的第一个字符开始遍历,遍历范围为 n - m + 1
  4. 对于每个位置 i,使用指针 j 遍历 needle ,并比较 haystack[i+j]needle[j] 的字符是否相等。如果相等,继续比较下一个字符;如果不相等,跳出循环。
  5. 如果 j 遍历到了 needle 的末尾,即 j == m,说明找到了第一个匹配项,返回当前指针 i 的值减去 needle 的长度 m
  6. 如果遍历完了 haystack 还没有找到匹配项,则返回 -1,表示 needle 不是 haystack 的一部分。

这样,我们就可以找到字符串 needle 在字符串 haystack 中的第一个匹配项的下标。

代码分析

在这里插入图片描述

  1. 首先,检查特殊情况,如果 needle 是空字符串,则直接返回下标 0,因为空字符串是任意字符串的子串。

  2. 计算 haystackneedle 的长度,分别赋值给变量 nm。这样做是为了避免在循环中多次访问 len() 函数。

  3. 使用外层循环 for i in range(n - m + 1) 遍历 haystack 的每个可能的起始位置。注意,外层循环的范围是 n - m + 1,因为当剩余的字符数小于 needle 的长度时,自然无法匹配。

  4. 在内层循环 for j in range(m) 中,使用指针 j 遍历 needle 的每个字符,并与 haystack 中对应位置的字符进行比较。如果字符相等,则继续比较下一个字符;如果字符不相等,则退出内层循环。

  5. 如果内层循环正常结束,即 j 遍历到了 needle 的末尾,说明找到了第一个匹配项,可以返回当前指针 i 的值。

  6. 如果外层循环结束后还没有找到匹配项,则返回 -1,表示 needle 不是 haystack 的子串。

这种算法的思路是逐个比较字符,直到找到匹配项或遍历完整个 haystack。在最坏情况下(没有匹配项或者匹配项在最后一个起始位置),需要进行大约 (n - m + 1) * m 次字符比较操作。

完整代码

在这里插入图片描述

class Solution(object):
	def strStr(self, haystack, needle):
	    if not needle:  # 特殊情况判断:needle为空字符串
	        return 0
	    
	    n = len(haystack)  # haystack长度
	    m = len(needle)  # needle长度
	
	    for i in range(n - m + 1):  # 遍历haystack的每个起始位置
	        for j in range(m):  # 遍历needle的每个字符
	            if haystack[i+j] != needle[j]:  # 当前字符不匹配,跳出内层循环
	                break
	        else:
	            return i  # 内层循环正常结束,找到匹配项,返回当前指针i的值
	    
	    return -1  # 未找到匹配项,返回-1

详细分析

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """

这段代码定义了一个名为 Solution 的类,并在类中定义了一个名为 strStr 的方法。strStr 方法接受两个参数 haystackneedle,它们分别表示被搜索的字符串和待搜索的子字符串。方法的返回类型声明为 int

        if not needle:
            return 0

这段代码首先检查特殊情况,即如果 needle 是空字符串,则直接返回 0。因为空字符串是任何字符串的子串。

        n = len(haystack)
        m = len(needle)

这段代码使用 len() 函数获取字符串 haystackneedle 的长度,并将它们分别存储在变量 nm 中。这样做是为了避免在后续循环中多次调用 len() 函数,从而提高效率。

        for i in range(n - m + 1):
            j = 0
            while j < m and haystack[i+j] == needle[j]:
                j += 1
            
            if j == m:
                return i

这段代码使用两个循环来实现字符串的匹配。外层循环使用 for 循环遍历 haystack 中每个可能的起始位置,范围是 n - m + 1。因为当剩余的字符数少于 needle 的长度时,无法进行匹配。

内层循环使用 while 循环,通过比较 haystack 中的字符和 needle 中的字符来进行匹配。循环条件为 j < m and haystack[i+j] == needle[j],表示当指针 j 小于 needle 的长度并且当前字符匹配时,继续循环。

如果内层循环正常结束,并且指针 j 的值等于 m,即遍历完了整个 needle,说明找到了匹配的子串,返回当前指针 i 的值。

        return -1

如果外层循环结束后仍然没有找到匹配项,则说明 needle 不是 haystack 的子串,返回 -1。

运行效果截图

调用示例

solution = Solution()
haystack = "sadbutsad"
needle = "sad"
haystack1 = "leetcode"
needle1 = "leeto"
print(solution.strStr(haystack, needle))
print(solution.strStr(haystack1, needle1))

运行结果

在这里插入图片描述

完结

在这里插入图片描述

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

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

相关文章

htmlCSS-----浮动

目录 前言&#xff1a; 浮动 1.浮动的效果 2.浮动的特点 3.浮动的写法 4.浮动的原理 5.浮动的作用 6.案例 7.浮动的缺陷与解决方式 浮动问题 解决方式 8.补充说明 前言&#xff1a; 浮动是html里面重要的一部分&#xff0c;前面我们学习了三种元素的类型&#xff08;…

计科web常见错误排错【HTTP状态404、导航栏无法点开、字符乱码及前后端数据传输呈现、jsp填写的数据传到数据库显示null、HTTP状态500】

web排错记录 在使用javaweb的过程中会出现的一些错误请在下方目录查找。 目录 错误1&#xff1a;HTTP状态404——未找到 错误2&#xff1a;导航栏下拉菜单无法点开的问题 错误3&#xff1a;字符乱码问题 错误4&#xff1a;jsp网页全部都是&#xff1f;&#xff1f;&#x…

Golang并发控制

开发 go 程序的时候&#xff0c;时常需要使用 goroutine 并发处理任务&#xff0c;有时候这些 goroutine 是相互独立的&#xff0c;需要保证并发的数据安全性&#xff0c;也有的时候&#xff0c;goroutine 之间要进行同步与通信&#xff0c;主 goroutine 需要控制它所属的子gor…

Linux系统安装部署MySQL完整教程(图文详解)

前言&#xff1a;最近网上翻阅了大量关于Linux安装部署MySQL的教程&#xff0c;在自己部署的时候总是存在一些小问题&#xff0c;例如&#xff1a;版本冲突&#xff0c;配置失败和启动失败等等&#xff0c;功夫不负有心人&#xff0c;最后还是安装部署成功了&#xff0c;所以本…

Ubuntu 网络配置指导手册

一、前言 从Ubuntu 17.10 Artful开始&#xff0c;Netplan取代ifupdown成为默认的配置实用程序&#xff0c;网络管理改成 netplan 方式处理&#xff0c;不在再采用从/etc/network/interfaces 里固定 IP 的配置 &#xff0c;配置写在 /etc/netplan/01-network-manager-all.yaml 或…

文本预处理——文本处理的基本方法

目录 什么是分词jieba分词特性精确模式分词全模式分词搜索引擎模式分词使用用户自定义词典 命名实体识别词性标注 什么是分词 jieba分词特性 精确模式分词 import jieba content工信处女干事每月经过下属科室都要亲口交代24口交换机等技术性器件的安装工作 print(jieba.lcut(co…

一文了解Python中的while循环语句

目录 &#x1f969;循环语句是什么 &#x1f969;while循环 &#x1f969;遍历猜数字 &#x1f969;while循环嵌套 &#x1f969;while循环嵌套案例 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &#x1f990;专栏地址&#xff1a;Python从入门到精通专栏 循环语句是什…

SpringBoot创建和使用

1.Spring Boot的优点 快速集成框架&#xff0c;Spring Boot提供了启动添加依赖的功能&#xff0c;用于秒级成各种框架。内置运行容器&#xff0c;无需配备Tomcat等Web容器&#xff0c;直接运行和部署程序。快速部署项目&#xff0c;无需外部容器即可启动并运行项目。可以完全抛…

概率论和随机过程的学习和整理--番外15,如何计算N合1的合成数量问题?

目录 1 目标问题&#xff1a;多阶2合1的合成问题 1.1 原始问题 1.2 合成问题要注意&#xff0c;合成的数量 1.3 合成问题不能用马尔科夫链来解决 2 方案1&#xff1a;用合成公式合成多次能解决吗&#xff1f; --不能&#xff0c;解决不了递归的问题 3 方案2&#xff0c;…

idea2021.安装pojie教程

1、下载ideaIU-2021.3应用包&#xff0c;点击finish 2、先关闭idea窗口&#xff0c;等会激活了脚本再运行打开。 3、双击运行install-current-user.vbs&#xff0c;等待一会会提示运行成功。 4、运行后&#xff0c;在文件中会多出一条配置 5、打开运行idea,输入激活码&#x…

如何使用curl下载github代码

首先通过chrome打开想要下载的源文件 如图&#xff0c;有那个下载图标时表示不需要鉴权即可下载&#xff0c;一般仓库都会开放只读权限&#xff0c;所以很大概率都有 比如我想下载这个crc32.c文件 那么我就需要知道它在哪个IP中&#xff0c;按下F12打开网络&#xff0c;点击下载…

pytorch安装GPU版本 (Cuda12.1)教程

使用本教程前&#xff0c;默认您已经安装并配置好了python3以上版本 1. 去官网下载匹配的Cuda Cuda下载地址 当前最高版本的Cuda是12.1 我安装的就是这个版本 小提示&#xff1a;自定义安装可以只选择安装Cuda Runtime。Nvidia全家桶不必全部安装。把全家桶全部安装完直接系统…

ChatGPT助力校招----面试问题分享(十二)

1 ChatGPT每日一题&#xff1a;运算放大器与比较器的区别 问题&#xff1a;运算放大器与比较器的区别 ChatGPT&#xff1a;运算放大器和比较器都是电子电路中常用的模拟电路元件&#xff0c;但它们的设计和应用略有不同。下面是两者的主要区别&#xff1a; 功能不同&#xf…

Java集合之List

ArrayLsit集合 ArrayList集合的特点 ArrayList集合的一些方法 ①.add(Object element) 向列表的尾部添加指定的元素。 ②.size() 返回列表中的元素个数。 ③.get(int index) 返回列表中指定位置的元素&#xff0c;index从0开始。 public class Test {public static void m…

【Vue】day03-VueCli(脚手架)

day03 一、今日目标 1.生命周期 生命周期介绍 生命周期的四个阶段 生命周期钩子 声明周期案例 2.综合案例-小黑记账清单 列表渲染 添加/删除 饼图渲染 3.工程化开发入门 工程化开发和脚手架 项目运行流程 组件化 组件注册 4.综合案例-小兔仙首页 拆分模块-局部…

有名管道(FIFO)的学习笔记

文章目录 有名管道介绍有名管道的使用创建 注意事项 有名管道介绍 有名管道的使用 创建 命令&#xff0c; mkfifo name函数&#xff0c;int mkfifo(const char *pathname, mode_t mode); 设置错误号&#xff1b; 向管道中写数据&#x1f447;&#xff1a; 从管道读数据&am…

前端Web实战:从零打造一个类Visio的流程图拓扑图绘图工具

前言 大家好&#xff0c;本系列从Web前端实战的角度&#xff0c;给大家分享介绍如何从零打造一个自己专属的绘图工具&#xff0c;实现流程图、拓扑图、脑图等类Visio的绘图工具。 你将收获 免费好用、专属自己的绘图工具前端项目实战学习如何从0搭建一个前端项目等基础框架项…

log4j--动态打印日志文件到指定文件夹

文章目录 log4j--动态打印日志文件到指定文件夹1、添加Maven依赖2、配置文件 log4j.properties3、编写日志打印工具类 LogUtil4、工具类调用 log4j–动态打印日志文件到指定文件夹 1、添加Maven依赖 <!-- log4j日志相关坐标 --><dependency><groupId>org.s…

API Testing 一个基于 YAML 文件的开源接口测试工具

目录 前言&#xff1a; 如何使用&#xff1f; 本地模式 服务端模式 文件格式 后续计划 前言&#xff1a; API Testing 是一个基于 YAML 文件的开源接口测试工具&#xff0c;它可以帮助开发者快速地进行接口测试。 在选择工具时&#xff0c;可以从很多方面进行考量、对比…

【Matlab】基于遗传算法优化 BP 神经网络的数据回归预测(Excel可直接替换数据)

【Matlab】基于遗传算法优化 BP 神经网络的数据回归预测&#xff08;Excel可直接替换数据&#xff09; 1.模型原理2.文件结构3.Excel数据4.分块代码4.1 arithXover.m4.2 delta.m4.3 ga.m4.4 gabpEval.m4.5 initializega.m4.6 maxGenTerm.m4.7 nonUnifMutation.m4.8 normGeomSel…