Leetcode #28. Implement strStr()

时间:2023-03-08 16:05:25

Implement strStr().

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

Brute Force算法,时间复杂度 O(mn)

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

Rabin karp算法时间复杂度可以降低到 O(mn) on average.

haystack: abcdefgh, needle: abc

needle_code = a + b*p + c*p^2 使用sliding window计算haystack_code可以节省计算量。

KMP算法也很快,但是面试一般无法完成。

 def charToInt(c):
return ord(c) - ord('a') + 1 def strStrRK(haystack, needle): m = len(haystack)
n = len(needle) if n == 0:
return 0
if m < n:
return -1 #choose a prime number as base
base = 29 needle_code = 0
for i in range(n):
needle_code += charToInt(needle[i]) * base**i lead = charToInt(haystack[0])
for j in range(m - n + 1): if j == 0:
haystack_code = 0
for i in range(n):
haystack_code += charToInt(haystack[j + i])*base**i
else:
haystack_code -= lead
haystack_code /= base
haystack_code += charToInt(haystack[j + n - 1])*base**(n-1)
lead = charToInt(haystack[j]) if haystack_code == needle_code:
if haystack[j:j + n] == needle:
return j return -1