28. 实现 strStr()

1.题目

2.解法

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null) {
            return -1;
        }
        // 没有needle 和 空字符串是两回事
        if (needle == null || needle.length() == 0) {
            return 0;
        }
        if (haystack.length() < needle.length()) {
            return -1;
        }

        int len = haystack.length();
        int nlen = needle.length();
        int k = 0;

        // 创建距离右边得位移数组
        int[] shift = new int[123];
        for (char c : needle.toCharArray()) {
            shift[c] = nlen - k++;
        }
            
        int i = 0;
        // 现在来遍历整个haystack数组, i + nlen,是下一轮字符串开始得首位
        while (i + nlen <= len) {
            if (getEquals(haystack, needle, i)) {
                return i;
            } else {
                // 有时候会遇到haystack=abccd， needle=cd这种情况
                // i + nlen < len 不能等于，等于数组都越界了，haystack没有charAt了
                // shift不存在得值，初始赋值都为0
                if (i + nlen < len && shift[haystack.charAt(i + nlen)] != 0) {
                    i += shift[haystack.charAt(i + nlen)];
                } else {
                    i += nlen;
                }
            }
        }
        return -1;
    }

    public boolean getEquals(String str1, String str2, int i) {
        for (int j = 0; j < str2.length(); j++) {
            // i是起始位置
            if (str2.charAt(j) != str1.charAt(i + j)) {
                return false;
            }
        }
        return true;
    }
}

这种方法耗时就，占内存
@1：时间复杂度O(len),len是haystack的长度， 因为（len/nlen）* nlen = len， 空间复杂度为O(n), n是shift数组的长度，所以不再是常量级
这道题，需要再看看

3.思考