From LeetCode 28. Implement strStr()


Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.


What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().


class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        a = len(needle)
        b = len(haystack)
        if a == 0:
            return 0
        next = self.getnext(a, needle)
        p = -1
        for j in range(b):
            while p>=0 and needle[p+1] != haystack[j]:
            if needle[p+1] == haystack[j]:
            if p == a-1:
                return j - a + 1
        return -1

    def getnext(self,a,needle):
        next = ['' for i in range(a)]
        k = -1
        next[0] = k
        for i in range(1, len(needle)):
            while (k > -1 and needle[k+1] != needle[i]):
                k = next[k]
            if needle[k+1] == needle[i]:
                k += 1
            next[i] = k
        return next