題目
實(shí)現(xiàn) strStr() 函數(shù)啸胧。
給定一個(gè) haystack 字符串和一個(gè) needle 字符串迎捺，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個(gè)位置 (從0開始)营搅。如果不存在筷转，則返回 -1蔚万。
示例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2
示例 2:
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
說明:
當(dāng) needle 是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢徽曲？這是一個(gè)在面試中很好的問題零截。
對(duì)于本題而言，當(dāng) needle 是空字符串時(shí)我們應(yīng)當(dāng)返回 0 秃臣。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符涧衙。
思路
這個(gè)題乍一看，難度是簡(jiǎn)單奥此？
最熟悉的字符串匹配弧哎，莫過于經(jīng)典的KMP了，理解透徹next數(shù)組怎么說也不能算是簡(jiǎn)單了吧得院？不過很快發(fā)現(xiàn)了簡(jiǎn)單的所在傻铣，可以使用內(nèi)置函數(shù)章贞，這樣一來祥绞，貌似就是一個(gè)優(yōu)雅與否的問題了
不過非洲，抱著這樣的態(tài)度，顯然不太行蜕径，因?yàn)樘岣咦约翰攀俏覀兿胍?br>
看了下大神們的答案两踏，我發(fā)現(xiàn)了BM算法 和 Sunday算法
這里簡(jiǎn)單說下自己對(duì)Sunday算法的理解吧,詳細(xì)的可以戳上面的鏈接看下：
從左往右遍歷對(duì)比
關(guān)注主串中參與匹配的最末位字符后面的那一位（下圖藍(lán)色位置）-
兩種情況如圖：
Case1 & 2 缺點(diǎn)是子串中大量重復(fù)時(shí)，效率變差最差
O(m*n)
再重復(fù)下兜喻，詳細(xì)請(qǐng)戳鏈接 BM算法 和 Sunday算法
自寫代碼
暴力版
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
if len(haystack) == 0:
return -1
#不用內(nèi)置函數(shù)梦染，直接以needle的長(zhǎng)度依次遍歷
for i in range(len(haystack)):
#真的，不要在循環(huán)套循環(huán)了朴皆，你不像個(gè)寫py的
if haystack[i:i+len(needle)] == needle:
return i
return -1
經(jīng)典的KMP算法
def kmp_search(self, haystack: str, needle: str) -> int:
def get_next(pattern: str):
j, k, l = 0, -1, len(pattern)
p_next = [-1 for _ in range(l)]
while j < l - 1:
if k == -1 or pattern[j] == pattern[k]:
k += 1
j += 1
if pattern[j] != pattern[k]:
p_next[j] = k
else:
p_next[j] = p_next[k]
else:
k = p_next[k]
return p_next
i, j, h_l, n_l = 0, 0, len(haystack), len(needle)
p_next = get_next(needle)
while i < h_l and j < n_l:
if j == -1 or haystack[i] == needle[j]:
i += 1
j += 1
else:
j = p_next[j]
if j == n_l:
return i - j
return -1
優(yōu)雅代碼
能兩行不來三行：
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:return 0
return haystack.index(needle) if needle in haystack else -1
sunday算法
def sunday_search(self, haystack: str, needle: str) -> int:
if not needle:
return 0
offset = {}
n_l = len(needle)
for i in range(n_l):
offset[needle[i]] = n_l - i
i, j, h_l = 0, 0, len(haystack)
while i <= h_l - n_l:
j = 0
while haystack[i + j] == needle[j]:
j += 1
if j == n_l:
return i
if i + n_l == h_l:
return -1
if haystack[i + n_l] in offset:
i += offset[haystack[i + n_l]]
else:
i += n_l + 1
return -1
自測(cè)反思
-
當(dāng) needle 是空字符串時(shí)帕识，我們應(yīng)當(dāng)返回什么值呢？
這句話在題目中給了提示遂铡，而這個(gè)確實(shí)是一個(gè)很好的問題肮疗，邊界，永遠(yuǎn)是測(cè)試重點(diǎn)扒接。 - 多個(gè)存在伪货，會(huì)不會(huì)出現(xiàn)問題？
- 不存在钾怔，會(huì)不會(huì)有問題碱呼？
以上，歡迎大家討論宗侦，共同進(jìn)步
歡迎大家關(guān)注我的公眾號(hào)
