28. 實現(xiàn) strStr()
題目來源：https://leetcode-cn.com/problems/implement-strstr
題目
實現(xiàn) strStr() 函數(shù)。
給定一個 haystack 字符串和一個 needle 字符串猪半，在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置 (從0開始)和二。如果不存在，則返回 -1亮元。
示例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2
示例 2:
輸入: haystack = "aaaaa", needle = "bba"
輸出: -1
說明:
當 needle 是空字符串時，我們應(yīng)當返回什么值呢？這是一個在面試中很好的問題戈轿。
對于本題而言症副，當 needle 是空字符串時我們應(yīng)當返回 0 店雅。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符政基。
解題思路
思路：雙指針
算法：
- 先找到 haystack 子串中第一個字符與 needle 字符串第一個字符相同的位置，從這里開始進行匹配闹啦；
- 逐個進行匹配沮明，當出現(xiàn)不匹配的字符時，考慮回溯窍奋，將 p 指針重置為此次匹配開始的下一位荐健，即是 p - cur_len + 1；
- 重復(fù)上面的過程琳袄，若完全匹配江场，則返回匹配子串的起始坐標，即是 p - N窖逗；最終都不匹配扛稽，則返回 -1。
（p 是指向 haystack 字符的指針滑负，q 是指向 needle 字符的指針在张，M 表示 haystack 字符的長度，N 表示 needle 字符的長度矮慕，cur_len 表示字符匹配的長度）
具體的過程如下圖所示：
圖解
代碼實現(xiàn)
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
M, N = len(haystack), len(needle)
if N == 0:
return 0
p = 0
while p < M - N + 1:
# 跳過子串首字符與 needle 首字符不同的字符
while p < M - N + 1 and haystack[p] != needle[0]:
p += 1
cur_len = 0
q = 0
# 開始匹配
while q < N and p < M and haystack[p] == needle[q]:
p += 1
q += 1
cur_len += 1
# 完全匹配帮匾，返回結(jié)果
if cur_len == N:
return p - N
# 不匹配，回溯痴鳄，重新匹配
p = p - cur_len + 1
return -1
實現(xiàn)結(jié)果
實現(xiàn)結(jié)果
以上就是使用雙指針的方法瘟斜，先找到子串與給定字符首字符相同的位置，同時遍歷痪寻，子串與字符進行匹配螺句，當不匹配時進行回溯，直到遍歷結(jié)束橡类，進而解決《實現(xiàn) strStr()》 問題的主要內(nèi)容蛇尚。
歡迎關(guān)注微信公眾號《書所集錄》
