28. 找出字符串中第一个匹配项的下标
目录
一、问题描述
给你两个字符串 haystack
和 needle
,请你在 haystack
字符串中找出 needle
字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle
不是 haystack
的一部分,则返回 -1
。
二、解题思路
我们要在字符串 haystack
中找到 needle
字符串的第一个出现位置。这里介绍两种方法:暴力匹配 和 KMP算法。
方法一:暴力匹配
- 遍历 haystack:我们依次从
haystack
字符串的每个位置开始,判断从当前字符开始的子串是否和needle
相等。 - 逐字符匹配:对于每个位置,检查从当前字符开始的子串和
needle
的每个字符是否相等。如果相等,则返回当前下标作为结果。 - 边界情况:如果
needle
的长度大于haystack
,则直接返回 -1。
方法二:KMP算法(效率更高)
KMP(Knuth-Morris-Pratt)算法通过提前计算出匹配失败时应该从哪里继续匹配,避免重复的匹配过程。
- 构建部分匹配表:首先构建一个部分匹配表,用来记录
needle
中每个位置的最长相同前后缀长度。 - 匹配过程:在匹配时,利用部分匹配表来决定失败后应该跳转到哪个位置,避免不必要的字符匹配。
三、代码
方法一:暴力匹配实现
class Solution {
public int strStr(String haystack, String needle) {
// 边界情况,如果 needle 为空,返回 0
if (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 开始的子串是否等于 needle
int j;
for (j = 0; j < nLen; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
break;
}
}
// 如果完全匹配,返回起始位置 i
if (j == nLen) {
return i;
}
}
// 如果没有匹配,返回 -1
return -1;
}
}
时间复杂度分析:
- 时间复杂度:O((n - m) * m),其中
n
是haystack
的长度,m
是needle
的长度。最坏情况下,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),大幅提升了效率。
原文地址:https://blog.csdn.net/weixin_61695887/article/details/142797361
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!