• 分类：String/TwoPointer
• 时间复杂度: O(n^2)
• 空间复杂度: O(1)

Rabin Karp解法:

• 时间复杂度: O(n+m)
• 空间复杂度: O(?)

125. Valid Palindrome

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()](https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf(java.lang.String).

代码：

解法1：

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        
        
        if haystack==None or needle==None:
            return -1
        
        len_h=len(haystack)
        len_n=len(needle)
        
        for i in range(len_h-len_n+1):
            j=0
            while j<len_n:
                if haystack[i+j]!=needle[j]:
                    break
                j+=1
            if j==len_n:
                return i
                     
        return -1

解法2 Rabin Karp算法：

class Solution:
    
    BASE=1000000
    
    def strStr(self, haystack: str, needle: str) -> int:
        
        
        if haystack==None or needle==None:
            return -1
        
        len_h=len(haystack)
        len_n=len(needle)
        
        if len_n==0:
            return 0
        
        power=1
        for i in range(len_n):
            power= (power * 31)%self.BASE
            
        needleCode=0
        for i in range(len_n):
            needleCode=(needleCode*31+ord(needle[i])-ord("a"))%self.BASE
        
        haystackCode=0
        for i in range(len_h):
            haystackCode=(haystackCode*31+ord(haystack[i])-ord("a"))%self.BASE
            if i<len_n-1:
                continue
            if i>=len_n:
                haystackCode=(haystackCode-(ord(haystack[i-len_n])-ord("a"))*power)%self.BASE
                if haystackCode<0:
                    haystackCode+=self.BASE
            if haystackCode==needleCode:
                k=0
                n=0
                for j in range(i-len_n+1,i+1):
                    if haystack[j]==needle[n]:
                        k+=1
                    n+=1
                if k==len_n:
                    return i-len_n+1
                     
        return -1

讨论：

1. 也是一道一看就知道要用two pointer的题目
2. 但是和125那道题不一样的地方在于这个是同向双指针，而且它check的地方是haystack[i+j]!=needle[j],这里是这样写，而不是i++之后再退回来（容易搞不清弄晕）
3. 到bug free用了N步：

• 一开始的判定条件有问题，应该是haystack==None or needle==None，而我使用了len==0，这就是出的问题，因为空串有一个隐形的”\n“...
• 之前haystack[i+j]!=needle[j]，这一步没有写好，搞的很复杂而且容易出bug

4. Rabin Karp算法是用了一个hash的算法，我觉得有点难，但是思路有意思，相当于从底层的角度帮我们了解了hash的运算法则。先是每个字母占一个31的空间，然后映射到10的6次方的空间里。
5. Rabin Karp这个解法我debug花了好长的时间，我觉得能bug free还是很难的。

• 首先needleCode和haystackCode的写法要统一，如上，先乘后加减最后模。
• 当两个code一样的时候是从i-len_n+1开始的，因为上面i-len_n已经减掉了
• 最后谨记最后一定要仔细的lo一眼代码确保bug free！