May I know why this python KMP solution timeout?


  • 0
    E

    Here is my KMP solution in Python. It passed 73/74 test cases but failed for the long 'aaaa...' one because of a timeout.

    class Solution(object):
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
            if not needle:
                return 0
    
            NEXT = get_next_array(needle)
            len_y = len(haystack)
            len_n = len(needle)
            n_index = 0
            i = 0
            while i < len_y and n_index < len_n:
    
                if haystack[i] == needle[n_index]:
                    n_index += 1
                    i += 1
                elif n_index > 0:
                    n_index = NEXT[n_index - 1] + 1
                else:
                    i += 1
    
            return i - len_n if n_index == len_n else -1
    
    
    def get_next(N, j):
        if j == 0:
            return -1
        i = get_next(N, j-1)
        while (N[i+1] != N[j] and i >= 0):
            i = get_next(N, i)
    
        return i + 1 if N[i+1] == N[j] else -1
    
    
    def get_next_array(s):
        r = [0] * len(s)
        for i, c in enumerate(s):
            r[i] = get_next(s, i)
        return r
    

    Appreciate if anyone could help to point out where I missed.

    Thanks a log guys!


  • 0
    E

    Found the reason finally. My get_next_array function is O(M*N) so that it timed out during generate the next array.

    Thanks to @gajni 's solution https://discuss.leetcode.com/topic/67730/o-m-n-and-o-mn-solutions which enlighten me.

    Here is the modified solution that accepted.

    class Solution:
        # @param {string} haystack
        # @param {string} needle
        # @return {integer}
        def strStr(self, haystack, needle):
            if not needle:
                return 0
    
            NEXT = get_next_array_v2(needle)
            len_y = len(haystack)
            len_n = len(needle)
            n_index = 0
            i = 0
            while i < len_y:
                c = haystack[i]
                if c == needle[n_index]:
                    n_index += 1
                    i += 1
    
                    if n_index == len_n:
                        return i - len_n
    
                if i < len_y and haystack[i] != needle[n_index]:
                    if n_index == 0:
                        i += 1
                    else:
                        n_index = NEXT[n_index - 1] + 1
    
            return -1
            
    def get_next_array_v2(s):
        len_s = len(s)
        r = [-1] * len_s
        pre_i, suf_i = 0, 1
        while suf_i < len_s:
            if s[pre_i] == s[suf_i]:
                r[suf_i] = pre_i
                pre_i += 1
                suf_i += 1
            elif pre_i:
                pre_i = r[pre_i - 1] + 1
            else:
                r[suf_i] = -1
                suf_i += 1
        return r
    

Log in to reply
 

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