28. 实现 strStr()

子串逐一比较

class Solution {
    public int strStr(String haystack, String needle) {
        int N = haystack.length();
        int L = needle.length();
        if (L == 0) {
            return 0;
        }
        for (int i = 0; i < N - L + 1; i++) {
            if (haystack.substring(i, i + L).equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

• 时间复杂度 O((N - L)L)，N 为 haystack 字符串长度，L 为 needle 字符串的长度
• 空间复杂度 O(1)

双指针

class Solution {
    public int strStr(String haystack, String needle) {
        int N = haystack.length();
        int L = needle.length();
        if (L == 0) {
            return 0;
        }
        for (int i = 0; i < N - L + 1; i++) {
            for (int j = 0; j < L; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
                if (j == L - 1) {
                    return i;
                }
            }
        }
        return -1;
    }
}

• 时间复杂度 O((N - L)L)，N 为 haystack 字符串长度，L 为 needle 字符串的长度
• 空间复杂度 O(1)

KMP

class Solution {
    public int strStr(String haystack, String needle) {
        int N = haystack.length();
        int L = needle.length();
        if (L == 0) {
            return 0;
        }
        haystack = " " + haystack;
        needle = " " + needle;
        int[] next = new int[L + 1];
        for (int i = 2, j = 0; i <= L; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j + 1)) {
                j = next[j];
            }
            if (needle.charAt(i) == needle.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
        for (int i = 1, j = 0; i <= N; 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 == L) {
                return i - L;
            }
        }
        return -1;
    }
}

• 时间复杂度 O(N + L)，N 为 haystack 字符串长度，L 为 needle 字符串的长度
• 空间复杂度 O(L)，L 为 needle 字符串的长度