力扣经典150题第二十三题:找出字符串中第一个匹配项的下标

本文主要是介绍力扣经典150题第二十三题:找出字符串中第一个匹配项的下标,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 力扣经典150题解析之二十三:找出字符串中第一个匹配项的下标
    • 1. 介绍
    • 2. 问题描述
    • 3. 示例
    • 4. 解题思路
    • 5. 代码实现
    • 6. 复杂度分析
    • 7. 测试与验证
    • 8. 总结
    • 9. 扩展

力扣经典150题解析之二十三:找出字符串中第一个匹配项的下标

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 仅由小写英文字符组成

3. 示例

示例输入:

haystack = "hello world"
needle = "world"

示例输出:

6

在目标字符串 “hello world” 中,子字符串 “world” 第一次出现在下标 6 的位置。

4. 解题思路

我们可以使用字符串匹配的经典算法来解决这个问题。一种简单的方法是使用暴力匹配算法:

  • 遍历目标字符串,对每个可能的起始位置进行匹配。
  • 每次匹配时,对比目标字符串中从当前起始位置开始的子字符串和待匹配的子字符串是否相同。
  • 如果找到匹配,返回当前起始位置;否则继续遍历。

这种方法的时间复杂度是 O(n * m),其中 n 是目标字符串的长度,m 是待匹配的子字符串的长度。

5. 代码实现

public class Solution {public int firstIndexOf(String haystack, String needle) {int n = haystack.length();int m = needle.length();for (int i = 0; i <= n - m; i++) {int j;for (j = 0; j < m; j++) {if (haystack.charAt(i + j) != needle.charAt(j)) {break;}}if (j == m) {return i;}}return -1; // 未找到匹配项}
}

6. 复杂度分析

  • 时间复杂度:O(n * m),其中 n 是目标字符串的长度,m 是待匹配的子字符串的长度。在最坏情况下,需要遍历所有可能的子字符串位置。
  • 空间复杂度:O(1),仅使用常数级别的额外空间。

7. 测试与验证

我们对示例输入进行测试:

public class Main {public static void main(String[] args) {Solution solution = new Solution();String haystack = "hello world";String needle = "world";int result = solution.firstIndexOf(haystack, needle);System.out.println("匹配项的下标为:" + result);}
}

输出结果为:

匹配项的下标为:6

8. 总结

通过实现字符串匹配算法,我们可以有效地找出字符串中第一个匹配项的下标。在实际应用中,字符串匹配是一个常见且重要的问题。这里我们使用了简单的暴力匹配算法,对目标字符串的每个可能起始位置进行了遍历匹配,找到第一个匹配项的下标。

9. 扩展

我们还可以探讨一些优化方案,如使用更高效的字符串匹配算法(例如 KMP 算法)来提高匹配的效率,或者讨论 Java 中字符串匹配方法的内部实现原理等。

希望本文能够帮助读者更好地理解字符串匹配问题及其解决方法。


这篇博客按照目录结构组织了问题描述、解题思路、代码实现和复杂度分析等内容,希望对您有所帮助!

这篇关于力扣经典150题第二十三题:找出字符串中第一个匹配项的下标的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/905758

相关文章

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Java 正则表达式URL 匹配与源码全解析

《Java正则表达式URL匹配与源码全解析》在Web应用开发中,我们经常需要对URL进行格式验证,今天我们结合Java的Pattern和Matcher类,深入理解正则表达式在实际应用中... 目录1.正则表达式分解:2. 添加域名匹配 (2)3. 添加路径和查询参数匹配 (3) 4. 最终优化版本5.设计思

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介