28 Implement strStr()

28. Implement strStr()

1. Question

Implement strStr().

Return the index of the first occurrence of needle in haystack, or-1if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"

Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"

Output: -1

2. Implementation

(1) KMP算法

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() == 0) {
            return 0;
        }

        if (haystack.length() < needle.length()) {
            return -1;
        }

        // KMP Algorithm
        int[] next = getNextArray(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 = next[j - 1];
            }
            else {
                ++i;
            }
        }

        if (j == needle.length()) {
            return i - needle.length();
        }

        return -1;
    }

    public int[] getNextArray(String pattern) {
        int[] next = new int[pattern.length()];

        int index = 0;

        for (int i = 1; i < pattern.length(); ) {
            if (pattern.charAt(i) == pattern.charAt(index)) {
                next[i] = index + 1;
                ++index;
                ++i;
            }
            else if (index != 0) {
                index = next[index - 1];
            }
            else {
                next[index] = 0;
                ++i;
            }
        }
        return next;
    }
}

(2) Two Pointers

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() == 0) {
            return 0;
        }

        int i = 0;
        while (i < haystack.length()) {
            if (haystack.length() - i < needle.length()) {
                break;
            }

            if (haystack.charAt(i) == needle.charAt(0)) {
                int j = i;
                while (j - i < needle.length() && haystack.charAt(j) == needle.charAt(j - i)) {
                    ++j;
                }

                if (j - i == needle.length()) {
                    return i;
                }
            }
            ++i;
        }
        return -1;
    }
}

3. Time & Space Complexity

KMP算法: 时间复杂度O(m + n), m是haystack的长度, n是needle的长度，空间复杂度O(n)

Two Pointers: 时间复杂度O(mn), 空间复杂度O(1)