题目

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

两种解法。

第一种：暴力直接求解，时间复杂度是O(n^2)。

第二种：Rabin-Karp算法。

时间复杂度O(m + n)。

代码

代码1

class Solution {

    public int strStr(String haystack, String needle) {

        if(haystack == null || needle == null) return -1;

        for(int i=0; i < haystack.length() - needle.length() + 1; i++){

            int j = 0;

            for(; j < needle.length(); j++){

                if(haystack.charAt(i + j) != needle.charAt(j)) break;

            }

            if(j == needle.length()) return i;

        }

        return -1;

    }

}

代码2

class Solution {

    static final int BASE = 1000000;

    public int strStr(String haystack, String needle) {

        if(haystack == null || needle == null) return -1;

        if(needle.length() == 0) return 0;

        int m = needle.length();

        //31 ^ m

        int power = 1;

        for (int i = 0; i < m; i++) {

            power = (power * 31) % BASE;

        }

        int targetCode = 0;

        for (int i = 0; i < m; i++) {

            targetCode = (targetCode * 31 + needle.charAt(i)) % BASE;

        }

        int hashCode = 0;

        for (int i = 0; i < haystack.length(); i++) {

            hashCode = (hashCode * 31 + haystack.charAt(i)) % BASE;

            if(i < m - 1){

                continue;

            }

            //减去开始的数 abcd - a

            if(i >= m) {

                hashCode = hashCode - (haystack.charAt(i - m) * power) % BASE;

                if(hashCode < 0){

                    hashCode += BASE;

                }

            }

            //双重校验

            if(hashCode == targetCode){

                if(haystack.substring(i - m + 1, i + 1).equals(needle)){

                    return i - m + 1;

                }

            }

        }

        return -1;

    }

}

巴特西

[算法]实现strStr()

题目

思路

代码

代码1

代码2

最新文章

热门文章