KMP, Python, 72 tests in 72 ms


  • 0
    N
    class Solution(object):
        def strStr(self, haystack, needle):
            """
            :type haystack: str
            :type needle: str
            :rtype: int
            """
    
            def _prefix(sub):
                """Create prefix table for substring aka needle."""
                f = [0] * len(sub)
                for i in xrange(1, len(sub)):
                    k = f[i - 1]
                    while k > 0 and sub[k] != sub[i]:
                        k = f[k - 1]
                    if sub[i] == sub[k]:
                        k += 1
                    f[i] = k
                return f
    
            if not haystack and not needle:
                return 0
    
            if haystack and not needle:
                return 0
    
            if len(needle) > len(haystack):
                return -1
    
            f = _prefix(needle)
            k = 0
            for i in xrange(len(haystack)):
                while k > 0 and haystack[i] != needle[k]:
                    k = f[k - 1]
                if haystack[i] == needle[k]:
                    k += 1
                if k == len(needle):
                    return i - len(needle) + 1
            return -1
    

Log in to reply
 

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