Implement strStr().

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

Example 1:


Input: haystack = "hello", needle = "ll"
Output: 2


Example 2:


Input: haystack = "aaaaa", needle = "bba"
Output: -1


Clarification:

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().

Difficulty: introductory

Starter code:

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        

Solutions:
class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if haystack == "" and needle == "":
             return 0
         if needle == "":
             return 0
         if haystack == "" or needle == "" or len(haystack.split(needle)) == 1:
             return -1
         return len(haystack.split(needle)[0])


class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         # if needle in haystack:
         #     for i in range(len(haystack)-len(needle)+1):
         #         if haystack[i:i+len(needle)]==needle:
         #             return i
         # else:
         #     return -1
         
         return haystack.find(needle)
             


class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         for i in range(len(haystack) - len(needle) + 1):
             if haystack[i:i + len(needle)] == needle:
                 return i
             
         return -1


class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if not needle:
             return 0
         
         for i in range(0, len(haystack)-len(needle)+1):
             match = True
             for j in range(len(needle)):
                 if haystack[i+j] != needle[j]:
                     match = False
                     break
             if match:
                 return i
         
         return -1


class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
        
         if needle == "":
             return 0           
         for i in range(len(haystack) - len(needle) + 1):
             for j in range(len(needle)):
                 if haystack[i+j] == needle[j]:
                     if j == len(needle) - 1:
                         return i             
                 else:
                     break
                         
         return -1
                 
                     


class Solution:
     def makeNext(self,s):
         k = -1; i = 0;
         next = [None for i in range(len(s))]
         next[0] = -1
         while(i < (len(s)-1)):
             while(k>=0 and s[i] != s[k]):
                 k = next[k]
             i += 1; k+= 1;
             if(s[i] == s[k]):
                 next[i] = next[k]
             else:
                 next[i] = k
         return next
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if(needle == ""):
             return 0
         Next = self.makeNext(needle)
         length = len(needle)
         
         for i in range(len(haystack)):
             count = 0
             while(haystack[i + count] == needle[count]):
                 count += 1 
                 if(count + i >= len(haystack)) and (count < length):
                     return -1
                     break
                 if (count >= length):
                     return i
                     break
         return -1
                 
         


class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if not needle:
             return 0
 
         nexts = [0] * len(needle)
         nexts[0] = -1;
         if len(needle) > 1:
             nexts[1] = 0;
         left = 0; right = 2;
         while right < len(needle):
             if needle[left] == needle[right - 1]:
                 nexts[right] = left + 1
                 left += 1
                 right += 1
             else:
                 if nexts[left] > 0:
                     left = nexts[left]
                 else:
                     nexts[right] = 0
                     left = 0
                     right += 1
 
         i = 0; j = 0
         while i <= len(haystack) - len(needle):
             if j == len(needle):
                 return i
 
             if haystack[i + j] == needle[j]:
                 j += 1
             else:
                 # ababdef   i=0
                 # ababc     j=4
                 # x0012
                 #   ababc   i=2,j=2
                 if nexts[j] > 0:
                     i = i + j - nexts[j]
                     j = nexts[j]
                 else:
                     i = i + 1
                     j = 0
 
         return -1
 


class Solution:
     def myNext(self, T):
         next = [-1]  # a next array with first is -1
         l = len(T)  # the kid str length
         i, j = 0, -1  # i is last , j is first
         while i < l:
             if j == -1 or T[i] == T[j]:
                 i += 1
                 j += 1
                 next.append(int(j))  # the same str
             else:
                 j = next[j]
         return next
 
     def strStr(self, haystack, needle):
         if needle == "":
             return 0
         arr = Solution().myNext(needle)
         l1 = len(haystack)
         l2 = len(needle)
         i, j = 0, 0
         while i < l1 and j < l2:
             if j == -1 or haystack[i] == needle[j]:
                 i += 1
                 j += 1
                 if j == l2:
                     return i - l2
             else:
                 j = arr[j]
         return -1

class Solution:
     def makeNext(self,s):
         k = -1; i = 0;
         next = [None for i in range(len(s))]
         next[0] = -1
         while(i < (len(s)-1)):
             while(k>=0 and s[i] != s[k]):
                 k = next[k]
             i += 1; k+= 1;
             if(s[i] == s[k]):
                 next[i] = next[k]
             else:
                 next[i] = k
         return next
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if(needle == ""):
             return 0
         Next = self.makeNext(needle)
         length = len(needle)
         
         for i in range(len(haystack)):
             count = 0
             while(haystack[i + count] == needle[count]):
                 count += 1 
                 if(count + i >= len(haystack)) and (count < length):
                     return -1
                     break
                 if (count >= length):
                     return i
                     break
         return -1
                 
         


class Solution(object):
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if len(haystack) == len(needle):
             if haystack == needle:
                 return 0
             else:
                 return -1
         
         for i in range(0,len(haystack)):
             k=i
             j=0
             while j<len(needle)  and k<len(haystack) and haystack[k] == needle[j]:
                 j+=1
                 k+=1
             if j==len(needle):
                 return i
         return -1 if needle else 0

class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
        
         if needle == "":
             return 0           
         for i in range(len(haystack) - len(needle) + 1):
             for j in range(len(needle)):
                 if haystack[i+j] == needle[j]:
                     if j == len(needle) - 1:
                         return i             
                 else:
                     break
                         
         return -1
                 
                     


class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if len(haystack) < len(needle):
             return -1
         if needle == '':
             return 0
         
         for i in range(len(haystack)):
             if haystack[i] == needle[0]:
                 res = True
                 j = 1
                 try:
                     while (j < len(needle)):
                         if haystack[i+j] == needle[j]:
                             j += 1
                         else:
                             res = False
                             break
                     if res:
                         return i
                 except:
                     return -1
         return -1

class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         
         # KMP
         i, j, m, n = -1, 0, len(haystack), len(needle)
         # construct jump array
         jump = [-1]*n
         while j < n-1: # j is increased by one
             if i == -1 or needle[i] == needle[j]:
                 i, j = i+1, j+1
                 jump[j] = jump[i] if needle[i]==needle[j] else i
             else:
                 i = jump[i]
         
         # swipe
         i, j = 0, 0 # both start at 0
         while i < m and j < n: # CAUTION j < n
             if j == -1 or haystack[i] == needle[j]:
                 i, j = i+1, j+1
             else:
                 j = jump[j]
         return i-j if j == n else -1

class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         next = self.next(needle)
         i = 0
         j = 0
         while i < len(haystack) and j < len(needle):
             if j == -1 or haystack[i] == needle[j]:
                 i += 1
                 j += 1
             else:
                 j = next[j]
         if j == len(needle):
             return i - j
         else:
             return -1
         
         
     def next(self, p):
         next = []
         next.append(-1)
         i = 0
         k = -1
         while i < len(p) - 1:
             if k == -1 or p[i] == p[k]:
                 i += 1
                 k += 1
                 next.append(k)
             else:
                 k = next[k]
         return next

class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         
         if not needle:
             return 0
         
         if not haystack:
             return -1
         
         if len(haystack) < len(needle):
             return -1
         
         N = len(haystack)
         for i in range(N):
             if needle == haystack[i:i+len(needle)]:
                 return i
         
         return -1
         


class Solution:
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if needle == '':
             return 0
         substr_len = len(needle)
         for index, char in enumerate(haystack):
             if haystack[index:index+substr_len] == needle:
                 return index
         return -1

class Solution:
     
     def prefixTable(self, s):
         t = [0 for _ in s]
         j = 0
         i = 1
         while i < len(s):
             if j == 0 and s[i] != s[j]:
                 t[i] = 0
                 i += 1
             elif s[i] == s[j]:
                 t[i] = j + 1
                 i += 1
                 j += 1
             elif j > 0 and s[j] != s[i]:
                 j = t[j-1]
         return t
 
     def find(self, text, pattern):
         ans = []
         t = self.prefixTable(pattern)
         i = j = 0
         while i < len(text):
             if text[i] == pattern[j]:
                 i += 1
                 j += 1
 
             if j == len(pattern):
                 ans.append(i - len(pattern))
                 j = t[j-1]
 
             elif i < len(text) and text[i] != pattern[j]:
                 if j > 0:
                     j = t[j-1]
                 else:
                     i += 1
         return ans
     
     def strStr(self, haystack, needle):
         """
         :type haystack: str
         :type needle: str
         :rtype: int
         """
         if len(needle) == 0:
             return 0
         ans = self.find(haystack, needle)
         return ans[0] if ans else -1
         # for i in range(len(haystack) - len(needle) + 1):
         #     if haystack[i: i + len(needle)] == needle:
         #         return i
         # return -1
         
         
         # for i in range(len(haystack) - len(needle) + 1):
         #     if haystack[i : i + len(needle)] == needle:
         #         return i
         # return -1