Return the index of the first occurrence of needle in haystack, or
needle is not part of
What should we return when
needle is an empty string? This is a great question to ask during an interview.
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]: p=next[p] if needle[p+1] == haystack[j]: p+=1 if p == a-1: return j - a + 1 return -1 def getnext(self,a,needle): next = ['' for i in range(a)] k = -1 next = 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