当前位置: 首页> 科技> 能源 > 网站建站网站开发_日本软银集团董事长_高清视频线转换线_我赢网客服系统

网站建站网站开发_日本软银集团董事长_高清视频线转换线_我赢网客服系统

时间:2025/7/11 15:14:41来源:https://blog.csdn.net/weixin_61695887/article/details/142797361 浏览次数:0次
网站建站网站开发_日本软银集团董事长_高清视频线转换线_我赢网客服系统

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析


一、问题描述

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

二、解题思路

我们要在字符串 haystack 中找到 needle 字符串的第一个出现位置。这里介绍两种方法:暴力匹配KMP算法

方法一:暴力匹配
  1. 遍历 haystack:我们依次从 haystack 字符串的每个位置开始,判断从当前字符开始的子串是否和 needle 相等。
  2. 逐字符匹配:对于每个位置,检查从当前字符开始的子串和 needle 的每个字符是否相等。如果相等,则返回当前下标作为结果。
  3. 边界情况:如果 needle 的长度大于 haystack,则直接返回 -1。
方法二:KMP算法(效率更高)

KMP(Knuth-Morris-Pratt)算法通过提前计算出匹配失败时应该从哪里继续匹配,避免重复的匹配过程。

  1. 构建部分匹配表:首先构建一个部分匹配表,用来记录 needle 中每个位置的最长相同前后缀长度。
  2. 匹配过程:在匹配时,利用部分匹配表来决定失败后应该跳转到哪个位置,避免不必要的字符匹配。

三、代码

方法一:暴力匹配实现

class Solution {public int strStr(String haystack, String needle) {// 边界情况,如果 needle 为空,返回 0if (needle.isEmpty()) {return 0;}// haystack 和 needle 的长度int hLen = haystack.length();int nLen = needle.length();// 如果 haystack 的长度小于 needle,无法匹配if (hLen < nLen) {return -1;}// 遍历 haystack 的每个可能的起点for (int i = 0; i <= hLen - nLen; i++) {// 对比 haystack 从 i 开始的子串是否等于 needleint j;for (j = 0; j < nLen; j++) {if (haystack.charAt(i + j) != needle.charAt(j)) {break;}}// 如果完全匹配,返回起始位置 iif (j == nLen) {return i;}}// 如果没有匹配,返回 -1return -1;}
}

时间复杂度分析:

  • 时间复杂度:O((n - m) * m),其中 nhaystack 的长度,mneedle 的长度。最坏情况下,needle 每次匹配都到最后一个字符才失败。
  • 空间复杂度:O(1),只用了常量空间来存储索引。

方法二:KMP算法实现

KMP 的详细实现可以在需要优化效率的情况下考虑。它的核心是通过构建部分匹配表来减少不必要的重复匹配,使得时间复杂度能达到 O(n)。

class Solution {public int strStr(String haystack, String needle) {if (needle.isEmpty()) {return 0;}int[] lps = buildLPS(needle);int i = 0, j = 0;while (i < haystack.length()) {if (haystack.charAt(i) == needle.charAt(j)) {i++;j++;}if (j == needle.length()) {return i - j;} else if (i < haystack.length() && haystack.charAt(i) != needle.charAt(j)) {if (j != 0) {j = lps[j - 1];} else {i++;}}}return -1;}private int[] buildLPS(String needle) {int[] lps = new int[needle.length()];int len = 0, i = 1;while (i < needle.length()) {if (needle.charAt(i) == needle.charAt(len)) {len++;lps[i] = len;i++;} else {if (len != 0) {len = lps[len - 1];} else {lps[i] = 0;i++;}}}return lps;}
}

KMP 方法的时间复杂度为 O(n + m),大幅提升了效率。

关键字:网站建站网站开发_日本软银集团董事长_高清视频线转换线_我赢网客服系统

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: