- 前言
- 题目
- 题解
- NO1：暴力匹配法(超时)
- NO2：KMP算法
- 参考文章
哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。
这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。
目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为字符串专题。
题目
题目来源leetcode
leetcode地址：28. 实现 strStr()，难度：简单。
题目描述(摘自leetcode)：
实现 strStr() 函数。 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。 说明： 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。 示例 1： 输入：haystack = "hello", needle = "ll" 输出：2 示例 2： 输入：haystack = "aaaaa", needle = "bba" 输出：-1 示例 3： 输入：haystack = "", needle = "" 输出：0 提示： 0 <= haystack.length, needle.length <= 5 * 104 haystack 和 needle 仅由小写英文字符组成
本地调试代码：
class Solution {
public int search(int[] nums, int target) {
....
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = new int[]{-1,0,3,5,9,12};//这里修改数组内容
System.out.println(solution.search(arr, 2));//数组、目标值
}
}
题解 NO1：暴力匹配法(超时)
思路：从前往后进行匹配，中间会使用一个临时节点来进行保存已经匹配的内容进行。
代码：
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null || "".equals(needle)) {
return 0;
}
for (int i = 0; i < haystack.length(); i++) {
int j = i;
int k = 0;
//临时保存中间与needle第一个字符相同的
int temp = -1;//若是下面没有匹配到就移动一格
while (k < needle.length() && j < haystack.length() && haystack.charAt(j) == needle.charAt(k)) {
if (j > i && haystack.charAt(j) == needle.charAt(0) && temp == -1) {
temp = j;
}
j++;
k++;
}
if (k == needle.length()) {
return i;
} else if (temp != -1) {
i = temp - 1;
}
}
return -1;
}
NO2：KMP算法
思路：若是查询的子串过长，不使用一些手段来过滤掉一些重复的操作就很容易超时。这里来使用KMP来获取前缀表并进行最长前后缀位置匹配，省略掉一些不需要重复进行比较的重复内容。
代码：时间复杂度O(m+n)
//构建前缀表
public void getNext(int[] next, String s) {
if (next.length > 0) {
int j = -1;
next[0] = j;
for (int i = 1; i < next.length; i++) {
//j实际表示当前字符串是否带有前缀的标记，>0表示有，则将当前位置内容与原本前缀后一个元素是否相同，若是相同
while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
j = next[j];
}
//用于进行更新当前前缀索引
if (s.charAt(i) == s.charAt(j + 1)) {
j++;
}
next[i] = j;
}
}
}
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null || "".equals(needle)) {
return 0;
}
int[] next = new int[needle.length()];
getNext(next, needle);
//当前匹配的子串索引位置，之后比较都是需要索引位置+1进行判断
int j = -1;
for (int i = 0; i < haystack.length(); i++) {
//根据前缀表来匹配最近的重复前缀位置
while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
j = next[j];
}
//haystack与needle指定位置比较，若是相同加一，说明该子串匹配通过
if (haystack.charAt(i) == needle.charAt(j + 1)) {
j++;
}
if (j == needle.length() - 1) {
return (i - needle.length() + 1);
}
}
return -1;
}
参考文章
[1]. leetcode题解
[2]. 代码随想录—28. 实现 strStr()
我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！
欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料
Q群：851968786 我们可以一起探讨学习
注明：转载可，需要附带上文章链接
