【leetcode】【初级算法】【字符串7】实现strStr（）

题目

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnr003/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

python题解

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        return haystack.find(needle)
1
2
3
4
5
6
7
8

java题解

Java中提供了四中查找方法：
1、int indexOf(String str) ：返回第一次出现的指定子字符串在此字符串中的索引。
2、int indexOf(String str, intstartIndex)：从指定的索引处开始，返回第一次出现的指定子字符串在此字符串中的索引。
3、int lastIndexOf(String str) ：返回在此字符串中最右边出现的指定子字符串的索引。
4、intlastIndexOf(String str, int startIndex)：从指定的索引处开始向后搜索，返回在此字符串中最后一次出现的指定子字符串的索引。

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}
1
2
3
4
5

暴搜

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        for(int i =0;i+m<n;i++){
            boolean flag = false;
            for(int j=0;j<m;j++){
                if(haystack.charAt(i+j)!=needle.charAt(j)){
                    flag = false;
                    break;
                }
            }
            if (flag){
                return i;
            }           
        }
        return -1 ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

kmp

 # 这里学习了kmp算法.命名是由三位发明者的名字首字母命名
        # kmp算法专门针对再字符串中找模式串的问题.
        # 核心思路:指针从头开始匹配,发现不匹配的元素值,直接跳转到最大前后缀位置,再进行比较.不用移动指向字符串的指针i,只用移动指向模式串的指针j(根据他的\每一位字符的最大前后缀数组next)
				class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if(m==0){
            return 0;
        }
        int[] pi = new int [m];
        for(int i=1,j=0;i<m;i++){
            while(j>0 && needle.charAt(i)!=needle.charAt(j)){
                j = pi[j-1];
            }
            if(needle.charAt(i) == needle.charAt(j)){
                j++;
            }
            pi[i] = j;
        }
        for(int i = 0,j=0;i<n;i++){
            while(j>0 && haystack.charAt(i)!= needle.charAt(j)){
                j = pi[j-1];
            }
            if(haystack.charAt(i) == needle.charAt(j)){
                j++;
            }
            if(j==m){
                return i-m+1;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33