Implement StrStr()

String
Easy

Approach

Diagrams

Analysis

Time

O(n + m)

Space

O(m)
class Solution:
    def strStr(self, haystack, needle):
        if not needle:
            return 0

        pattern = self.buildPattern(needle)
        return self.needleIsInHaystack(haystack, needle, pattern)

    def buildPattern(self, needle):
        pattern = [-1] * len(needle)

        j = 0
        i = 1

        while i < len(needle):
            if needle[i] == needle[j]:
                pattern[i] = j
                i += 1
                j += 1
            elif j > 0:
                j = pattern[j - 1] + 1
            else:
                i += 1

        return pattern

    def needleIsInHaystack(self, haystack, needle, pattern):
        i = 0
        j = 0

        while i + len(needle) - j <= len(haystack):
            if haystack[i] == needle[j]:
                if j == len(needle) - 1:
                    return i - j
                i += 1
                j += 1
            elif j > 0:
                j = pattern[j - 1] + 1
            else:
                i += 1

        return -1

Learn

#Knuth-Morris-Pratt

Videos