28. Implement strStr()

Posted on | Edited on | Views:

LeetCode

Approach 1: Substring: Linear Time Slice

1
2
3
4
5
6
7
8
9
class Solution {
    public int strStr(String haystack, String needle) {
        int l=needle.length(),n=haystack.length();
        for(int i=0;i<n-l+1;i++){
            if(haystack.substring(i,i+l).equals(needle)) return i;
        }
        return -1;
    }
}

Approach 2: Two Pointers: Linear Time Slice link

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int strStr(String haystack, String needle) {
        int l=needle.length(),n=haystack.length();
        if(l==0) return 0;
        for(int i=0;i<n-l+1;i++){
            for(int j=0;j<l&&haystack.charAt(i+j)==needle.charAt(j);j++){
                if(j==l-1) return i;
            }
        }
        return -1;
    }
}

Approach 3: Rabin Karp (rolling hash): Constant Time Slice, Time complexity: O(N) youtube

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
34
35
36
37
38
39
40
41
class Solution {
    private boolean isMatch(String a,String b,int start){
        for(int i=0;i<b.length();i++){
            if(a.charAt(i+start)!=b.charAt(i)) return false;
        }
        return true;
    }
    // function to convert character to integer
    public int charToInt(int idx, String s) {
        return (int) s.charAt(idx) - (int) 'a';
    }

    public int strStr(String haystack, String needle) {
        int n = haystack.length(),l = needle.length();
        if (n<l) return -1;

        // base value for the rolling hash function
        int base = 26;
        // modulus value for the rolling hash function to avoid overflow
        long modulus = (long) Math.pow(2, 31);

        // compute the hash of strings haystack[:l], needle[:l]
        long h = 0, ref_h = 0;
        for (int i = 0; i < l; ++i) {
            h = (h * base + charToInt(i, haystack)) % modulus;
            ref_h = (ref_h * base + charToInt(i, needle)) % modulus;
        }
        if (h == ref_h && isMatch(haystack, needle, 0)) return 0;

        // const value to be used often : base**l % modulus
        long aL = 1;
        for (int i = 1; i <= l; ++i) aL = (aL * base) % modulus;

        for (int start = 1; start < n - l + 1; ++start) {
            // compute rolling hash in O(1) time
            h = (h * base - charToInt(start - 1, haystack) * aL + charToInt(start + l - 1, haystack)) % modulus;
            if (h == ref_h && isMatch(haystack, needle, start)) return start;
        }
        return -1;
    }
}

Approach 4: KMP pattern matching, Time Complexity: O(m+n) youtube

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
34
class Solution {
    private int[] kmpPreprocess(String pattern) {
        int i = 1, j = 0;
        int[] res = new int[pattern.length()];
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                res[i] = j + 1;
                i++; j++;
            } else if (j > 0) {
                j = res[j - 1];
            } else {
                res[i] = 0;
                i++;
            }
        }
        return res;
    }

    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null || needle.length() > haystack.length()) return -1;
        int[] kmp = kmpPreprocess(needle);
        int i = 0, j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++; j++;
            } else if (j > 0) {
                j = kmp[j - 1];
            } else {
                i++;
            }
        }
        return j == needle.length() ? i - j : -1;
    }
}

0%