LeetCode in Python 28. Implement strStr - Michelle小梦想家

打卡😎😎

小姐姐好。这道题我有一个诡异的方法😂😂😂😂
def strStr(self, haystack, needle):
return haystack.find(needle)
Runtime: 36 ms, faster than 85.35% of Python3 online submissions for Implement strStr().
Memory Usage: 13.3 MB, less than 5.13% of Python3 online submissions for Implement strStr().

这道题我一开始想用sliding window做，后来发现不可行。
例如
haystack=‘ccccd’
needle='cccd'
没办法跳过第四个c，只能逐个扫描。

for i in range(len(haystack) - len(needle) + 1):

Michelle你好，我一直想不明白为什么需要 +1。但是，如果删去 +1的话，跑 needle = "" 的时候会是错误的output

这个题 用KMP方法讲讲吧

请问小姐姐，为什么这题不讨论edge case呢？ 我觉得应该在for loop 前加入：@Michelle小梦想家
if len(needle） == 0:
return 0
if len(haystack) == 0 :
return -1
else:
for ...

这个题的Java解法,但我觉得没有任何意义啊:


public int strStr(String haystack, String needle) {
if ( needle.length() == 0) return 0;
if ( haystack.length() == 0) return -1;

if (haystack.contains(needle)){
return haystack.indexOf(needle);
}
return -1;

}

這解法也太好！相比官網上又臭又長的解法 lol

class Solution:
def strStr(self, haystack: str, needle: str) -> int:
L, n = len(needle), len(haystack)
if L > n:
return -1

# base value for the rolling hash function
a = 26
# modulus value for the rolling hash function to avoid overflow
modulus = 2**31

# lambda-function to convert character to integer
h_to_int = lambda i : ord(haystack[i]) - ord('a')
needle_to_int = lambda i : ord(needle[i]) - ord('a')

# compute the hash of strings haystack[:L], needle[:L]
h = ref_h = 0
for i in range(L):
h = (h * a + h_to_int(i)) % modulus
ref_h = (ref_h * a + needle_to_int(i)) % modulus
if h == ref_h:
return 0

# const value to be used often : a**L % modulus
aL = pow(a, L, modulus)
for start in range(1, n - L + 1):
# compute rolling hash in O(1) time
h = (h * a - h_to_int(start - 1) * aL + h_to_int(start + L - 1)) % modulus
if h == ref_h:
return start

return -1

您好，我想问一下中间if语句哪里为什么不是 haystack[ i : i+len(needle) -1], i 不是从0开始的吗，这样假如needle 长度为2 就是[1:3]三位数了

解法必须看Michelle的，看别人的我咳嗽