【LeetCode】28. 找出字符串中第一个匹配项的下标(KMP & String类)
2023-12-21 17:19:54
??今日学习的文章链接和视频链接
leetcode题目地址:28. 找出字符串中第一个匹配项的下标
?代码随想录题解地址:代码随想录
题目简介
给你两个字符串?haystack
?和?needle
?,请你在?haystack
?字符串中找出?needle
?字符串的第一个匹配项的下标(下标从 0 开始)。如果?needle
?不是?haystack
?的一部分,则返回??-1
?。
看到题目的第一想法(可以贴代码)
1. 遍历长字符串,将每一位与短字符串的首字符进行比较,若相等,则继续判断是否包含整个短字符串,并返回下标。
public int strStr(String haystack, String needle) {
int len1 = haystack.length();
int len2 = needle.length();
char[] c1 = haystack.toCharArray();
char[] c2 = needle.toCharArray();
boolean check = true;
for (int i=0; i<=len1-len2; i++){
if(c1[i] == c2[0]){
for(int j=0; j<len2; j++){
if (c2[j] != c1[i+j]) {
check = false;
break;
}
}
if (check) return i;
check = true;
}
}
return -1;
}
实现过程中遇到哪些困难
无
看完代码随想录之后的想法
【解题思路】KMP解法
? ? ? ? 最长公共前后缀,next数组。
看完视频自己写的ACC:
// KMP实现方法
public void getNext(int[] next, String s){
int j = -1;
next[0] = j;
for (int i=1; i<s.length(); i++){
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 (needle.length() == 0) return 0;
int[] next = new int[needle.length()];
getNext(next, needle);
int j = -1;
for (int i=0; i<haystack.length(); i++){
while (j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
j = next[j];
}
if (haystack.charAt(i) == needle.charAt(j+1)) {
j++;
}
if (j == needle.length() - 1) {
return (i-needle.length()+1);
}
}
return -1;
}
学习时长
略
今日收获
1. int[]的打印:System.out.println( Arrays.toString(intarr) );
2. Java String类常用方法
文章来源:https://blog.csdn.net/Leonardo_t/article/details/135115414
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!