Java and Python solution using KMP with O(m + n) time complexity


  • 7
    C

    The time complexity for this solution should be O(m + n). First of all, we generate the "next" array to show any possible duplicates of prefix and postfix within needle. Then we go through haystack. Every time we see a bad match, move j to next[j] and keep i in current position; otherwise, move both of them to next position.
    Python version:

    def strStr(self, haystack, needle):
        if haystack == None or needle == None:
            return -1
        #generate next array, need O(n) time
        i, j, m, n = -1, 0, len(haystack), len(needle)
        next = [-1] * n
        while j < n - 1:  
            #needle[k] stands for prefix, neelde[j] stands for postfix
            if i == -1 or needle[i] == needle[j]:   
                i, j = i + 1, j + 1
                next[j] = i
            else:
                i = next[i]
            print i,j,next[i],next[j]
        #check through the haystack using next, need O(m) time
        i = j = 0
        while i < m and j < n:
            if j == -1 or haystack[i] == needle[j]:
                i, j = i + 1, j + 1
            else:
                j = next[j]
        if j == n:
            return i - j
        return -1
    

    Java version:

    public int strStr(String haystack, String needle){
        if (haystack == null || needle == null)
            return -1;
        //generate next array, need O(n) time
        int i = -1, j = 0, m = haystack.length(), n = needle.length();
        int[] next = new int[n];
        if (next.length > 0) 
            next[0] = -1;
        while (j < n - 1) {
            if (i == -1 || needle.charAt(i) == needle.charAt(j))
                next[++j] = ++i;
            else 
                i = next[i];
        }
        //check through the haystack using next, need O(m) time
        i = 0; j = 0;
        while (i < m && j < n) {
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            else 
                j = next[j];
        }
        if (j == n)
            return i - j;
        return -1;
    }

Log in to reply
 

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