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

1char charAt(int index)
返回指定索引处的 char 值。
2int compareTo(Object o)
把这个字符串和另一个对象比较。
3int compareTo(String anotherString)
按字典顺序比较两个字符串。
4int compareToIgnoreCase(String str)
按字典顺序比较两个字符串,不考虑大小写。
5String concat(String str)
将指定字符串连接到此字符串的结尾。
6boolean contentEquals(StringBuffer sb)
当且仅当字符串与指定的StringBuffer有相同顺序的字符时候返回真。
7static String copyValueOf(char[] data)
返回指定数组中表示该字符序列的 String。
8static String copyValueOf(char[] data, int offset, int count)
返回指定数组中表示该字符序列的 String。
9boolean endsWith(String suffix)
测试此字符串是否以指定的后缀结束。
10boolean equals(Object anObject)
将此字符串与指定的对象比较。
11boolean equalsIgnoreCase(String anotherString)
将此 String 与另一个 String 比较,不考虑大小写。
12byte[] getBytes()
?使用平台的默认字符集将此 String 编码为 byte 序列,并将结果存储到一个新的 byte 数组中。
13byte[] getBytes(String charsetName)
使用指定的字符集将此 String 编码为 byte 序列,并将结果存储到一个新的 byte 数组中。
14void getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin)
将字符从此字符串复制到目标字符数组。
15int hashCode()
返回此字符串的哈希码。
16int indexOf(int ch)
返回指定字符在此字符串中第一次出现处的索引。
17int indexOf(int ch, int fromIndex)
返回在此字符串中第一次出现指定字符处的索引,从指定的索引开始搜索。
18int indexOf(String str)
?返回指定子字符串在此字符串中第一次出现处的索引。
19int indexOf(String str, int fromIndex)
返回指定子字符串在此字符串中第一次出现处的索引,从指定的索引开始。
20String intern()
?返回字符串对象的规范化表示形式。
21int lastIndexOf(int ch)
?返回指定字符在此字符串中最后一次出现处的索引。
22int lastIndexOf(int ch, int fromIndex)
返回指定字符在此字符串中最后一次出现处的索引,从指定的索引处开始进行反向搜索。
23int lastIndexOf(String str)
返回指定子字符串在此字符串中最右边出现处的索引。
24int lastIndexOf(String str, int fromIndex)
?返回指定子字符串在此字符串中最后一次出现处的索引,从指定的索引开始反向搜索。
25int length()
返回此字符串的长度。
26boolean matches(String regex)
告知此字符串是否匹配给定的正则表达式。
27boolean regionMatches(boolean ignoreCase, int toffset, String other, int ooffset, int len)
测试两个字符串区域是否相等。
28boolean regionMatches(int toffset, String other, int ooffset, int len)
测试两个字符串区域是否相等。
29String replace(char oldChar, char newChar)
返回一个新的字符串,它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。
30String replaceAll(String regex, String replacement)
使用给定的 replacement 替换此字符串所有匹配给定的正则表达式的子字符串。
31String replaceFirst(String regex, String replacement)
?使用给定的 replacement 替换此字符串匹配给定的正则表达式的第一个子字符串。
32String[] split(String regex)
根据给定正则表达式的匹配拆分此字符串。
33String[] split(String regex, int limit)
根据匹配给定的正则表达式来拆分此字符串。
34boolean startsWith(String prefix)
测试此字符串是否以指定的前缀开始。
35boolean startsWith(String prefix, int toffset)
测试此字符串从指定索引开始的子字符串是否以指定前缀开始。
36CharSequence subSequence(int beginIndex, int endIndex)
?返回一个新的字符序列,它是此序列的一个子序列。
37String substring(int beginIndex)
返回一个新的字符串,它是此字符串的一个子字符串。
38String substring(int beginIndex, int endIndex)
返回一个新字符串,它是此字符串的一个子字符串。
39char[] toCharArray()
将此字符串转换为一个新的字符数组。
40String toLowerCase()
使用默认语言环境的规则将此 String 中的所有字符都转换为小写。
41String toLowerCase(Locale locale)
?使用给定 Locale 的规则将此 String 中的所有字符都转换为小写。
42String toString()
?返回此对象本身(它已经是一个字符串!)。
43String toUpperCase()
使用默认语言环境的规则将此 String 中的所有字符都转换为大写。
44String toUpperCase(Locale locale)
使用给定 Locale 的规则将此 String 中的所有字符都转换为大写。
45String trim()
返回字符串的副本,忽略前导空白和尾部空白。
46static String valueOf(primitive data type x)
返回给定data type类型x参数的字符串表示形式。
47contains(CharSequence chars)
判断是否包含指定的字符系列。
48isEmpty()
判断字符串是否为空。

文章来源:https://blog.csdn.net/Leonardo_t/article/details/135115414
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。