【LeetCode】28. 找出字符串中第一个匹配项的下标(KMP & String类)

??今日学习的文章链接和视频链接

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类常用方法