Ac solution code


  • 0

    This solution is based on KMP algorithm.

    Time complexity = O(n + m)

    KMP pre-process the pattern, and saves if ith character doesn't match, what's the next position to check, to avoid duplicated comparasions.

    Runtime of brute force: O(n * m), so KMP is much faster!

    JAVA Code:

    public int strStr(String haystack, String needle) {
        //KMP algorithms
        if(needle.equals("")) return 0;
        if(haystack.equals("")) return -1;
        char[] arr = needle.toCharArray();
        int[] next = makeNext(arr);
    
        for(int i = 0, j = 0, end = haystack.length(); i < end;){
            if(j == -1 || haystack.charAt(i) == arr[j]){
                j++;
                i++;
                if(j == arr.length) return (i - arr.length);
            }
            if(i < end && haystack.charAt(i) != arr[j]) 
                j = next[j]; //<--Use prefix length
        }
        return -1;
    }
    
    //Pre-process the pattern string, to get the prefix length for each position i in the pattern string
    private int[] makeNext(char[] arr){
        int len = arr.length;
        int[] next = new int[len];
    
        next[0] = -1;
        for(int i = 0, j = -1; i + 1 < len;){
            if(j == -1 || arr[i] == arr[j]){
                next[i+1] = j+1;
                if(arr[i+1] == arr[j+1]) next[i+1] = next[j+1];
                i++;
                j++;
            }
            if(arr[i] != arr[j]) j = next[j];
        }
    
        return next;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.