28. Implement strStr() / strStr II

Version #2 Rabin Karp

O(m + n)
28.58 %
class Solution {
    public int BASE = 1000000;
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null) return -1;
        if (needle.length() == 0) return 0;
     
        int target = 0;
        int power = 1; // weight of the highest bit
        int len = needle.length();
        for (int i = 0; i < len; i++) {
            target = (target * 31 + Character.getNumericValue(needle.charAt(i))) % BASE;
            power = power * 31 % BASE;
        }
        int hashCode = 0;
        for (int j = 0; j < haystack.length(); j++) {
            //       j = 3, len = 3
            // abc + d
            hashCode = (hashCode * 31 + Character.getNumericValue(haystack.charAt(j))) % BASE;
            // delete (j - len)
            if (j >= len) {
                hashCode = (hashCode - Character.getNumericValue(haystack.charAt(j - len)) * power) % BASE;
                if (hashCode < 0) hashCode += BASE;
            }
         
         
            if (hashCode == target) {
                // double check to ensure correctness
                //haystack index [j - len + 1, j]
                if (haystack.substring(j - len + 1, j + 1).equals(needle)) return j - len + 1;
            }
        }
        return -1;
    }
}


Version #1 KMP
看了普林斯顿老爷爷的讲解感觉理解的比较深刻了，但是自己写还是不熟练
LeetCode上面有一个人dfa只用了一维数组，没懂为何
https://discuss.leetcode.com/topic/3576/accepted-kmp-solution-in-java-for-reference

网上另一个讲解

暂时先这样吧以后有空再看看

public class Solution {
    /**
     * @param source a source string
     * @param target a target string
     * @return an integer as index
     */
    public int strStr2(String source, String target) {
        // Write your code here
        if (source == null || target == null || source.length() < target.length()) return -1;
        if (target.length() == 0) return 0;
        int i, j, N = source.length(), M = target.length();
        int[][] dfa = dfaBuilder(target);
        for (i = 0, j = 0; i < N && j < M; i++) {
            j = dfa[source.charAt(i) - 'a'][j];
        }
        if (j == M) return i - M;
        return -1;
    }
 
    public int[][] dfaBuilder(String target) {
        int M = target.length();
        int R = 26; //ASCII
        int[][] dfa = new int[R][M];
        dfa[target.charAt(0) - 'a'][0] = 1; //The 1st match state
        for (int x = 0, j = 1; j < M; j++) {
            for (int c = 0; c < R; c++) {
                dfa[c][j] = dfa[c][x]; //copy mismatch cases
                dfa[target.charAt(j) - 'a'][j] = j + 1; //set the match case
                x = dfa[target.charAt(j) - 'a'][x];
            }
        }
        return dfa;
    }
}

二刷

Version #1 Brute Force

Runtime: 0 ms, faster than 100.00% of Java online submissions for Implement strStr().

Memory Usage: 40.3 MB, less than 90.37% of Java online submissions for Implement strStr().

Time O(mn)

class Solution {

    public int strStr(String haystack, String needle) {

        if (haystack == null || needle == null || needle.equals("")) {

            return 0;

        }

        

        int needleLen = needle.length();

        int haystackLen = haystack.length();

        for (int start = 0; start + needleLen <= haystackLen; start++) {

            if (matches(haystack, start, needle)) {

                return start;

            }

        }

        return -1;

    }

    

    // abcde

    // qqqqabcde

    private boolean matches(String source, int start, String target) {

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

            if (start + i >= source.length()) {

                return false;

            }

            if (source.charAt(start + i) != target.charAt(i)) {

                return false;

            }

        }

        return true;

    }

}