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