实现 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()
定义相符。
直观的解法的是:枚举原串 ss
中的每个字符作为起点,构造一个和匹配串 pp
一样长度的子串 sub
,将 sub
和 pp
做对比:
class Solution {
public int strStr(String ss, String pp) {
int n = ss.length(), m = pp.length();
for (int i = 0; i < n - m + 1; i++) {
String sub = ss.substring(i, i + m);
if (sub.equals(pp)) return i;
}
return -1;
}
}
n
为原串的长度,m
为匹配串的长度。其中枚举的复杂度为 ,构造和比较字符串的复杂度为
。整体复杂度为
KMP 算法是一个快速查找匹配串的算法,时间复杂度为
。
建议和三叶在「5. 最长回文子串」中提供的 Manacher 算法一样,进行背过。
KMP 算法的应用范围要比 Manacher 算法要广,Manacher 算法只能应用于「回文串」问题,较为局限,而「子串匹配」问题还是十分常见的。
背过这样的算法的意义在于:相当于大脑里有了一个时间复杂度为
的 api 可以使用,这个 api 传入一个原串和匹配串,返回匹配串在原串的位置。
一些相关的注释我已经写到代码里:
class Solution {
// KMP 算法
// ss: 原串 pp: 匹配串
public int strStr(String ss, String pp) {
if (pp.isEmpty()) return 0;
// 分别读取原串和匹配串的长度
int n = ss.length(), m = pp.length();
// 原串和匹配串前面都加空格,使其下标从 1 开始
ss = " " + ss;
pp = " " + pp;
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
// 构建 next 数组,数组长度为匹配串的长度(next 数组是和匹配串相关的)
int[] next = new int[m + 1];
// 构造过程 i = 2,j = 0 开始,i 小于等于匹配串长度 【构造 i 从 2 开始】
for (int i = 2, j = 0; i <= m; i++) {
// 匹配不成功的话,j = next(j)
while (j > 0 && p[i] != p[j + 1]) j = next[j];
// 匹配成功的话,j++
if (p[i] == p[j + 1]) j++;
next[i] = j;
}
// 匹配过程,i = 1,j = 0 开始,i 小于等于原串长度 【匹配 i 从 1 开始】
for (int i = 1, j = 0; i <= n; i++) {
// 匹配不成功 j = next(j)
while (j > 0 && s[i] != p[j + 1]) j = next[j];
// 匹配成功 j++
if (s[i] == p[j + 1]) j++;
// 如果匹配成功了,直接返回
if (j == m) return i - m;
}
return -1;
}
}
next
数组。复杂度为这是我们「刷穿 LeetCode」系列文章的第 No.28
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 28/1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。