題目描述
實作一個函數 strStr(haystack, needle)，用來找出字串 needle 在字串 haystack 中第一次出現的索引。如果 needle 不是 haystack 的一部分，則返回 -1。
範例 1：
輸入：haystack = "sadbutsad", needle = "sad"輸出：
0解釋：needle 出現在 haystack 的索引 0 和 6 處。第一次出現在索引 0 處，所以回傳 0。
範例 2：
輸入：
haystack = "leetcode", needle = "leeto"
輸出：
-1
解釋：needle 不在 haystack 中。
解題思路
要解決這個問題，我們需要從以下角度考慮：
- 字串匹配：找到
needle是否存在於haystack中。 - 返回索引：如果匹配成功，返回第一個字符的索引；否則返回
-1。
我們可以從最簡單的暴力匹配到更高效的演算法（如 KMP 演算法）進行討論。
解法一：暴力解法
思路
使用兩層迴圈：
- 外層迴圈遍歷
haystack的每個字符作為起始位置。 - 內層迴圈檢查從該起始位置開始的子字串是否與
needle匹配。
詳細步驟
- 檢查特殊情況：
- 如果 needle 是空字串，返回 0。
- 如果 needle 長度大於 haystack，直接返回 -1。
- 遍歷
haystack： - 如果從當前索引開始的子字串與 needle 匹配，返回當前索引。
- 如果遍歷結束仍無匹配，返回 -1。
程式碼實現
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
m, n = len(haystack), len(needle)
for i in range(m - n + 1):
if haystack[i:i + n] == needle:
return i
return -1
時間與空間複雜度
- 時間複雜度：O((m−n+1)⋅n)，其中 m 是
haystack的長度，n 是needle的長度。 - 外層迴圈最多執行 m−n+1 次。
- 內層迴圈每次檢查 n 個字符。
- 空間複雜度：O(1)，未使用額外空間。
解法二：KMP 演算法（Knuth-Morris-Pratt Algorithm）
思路
暴力解法在每次失敗匹配時會回退至下一個起始位置，這會導致重複計算。KMP 演算法通過預處理 needle，構建一個「部分匹配表」（partial match table），在匹配失敗時快速跳過不必要的字符。
部分匹配表（LPS）的構建
LPS（Longest Prefix which is also Suffix）表記錄了 needle 的每個字符之前的最長前綴後綴匹配長度。
步驟：
- 初始化一個長度為
n的數組lps，所有值為 0。 - 遍歷
needle，更新前綴後綴匹配長度。
詳細步驟
- 構建 LPS 表。
- 使用兩個指針進行匹配：
- 一個指向 haystack（主串）。
- 一個指向 needle（模式串）。
當匹配失敗時，根據 LPS 表跳過多餘的字符。
程式碼實現
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
def buildLPS(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = buildLPS(needle)
i = j = 0
while i < len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1
if j == len(needle):
return i - j
elif i < len(haystack) and haystack[i] != needle[j]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
時間與空間複雜度
- 時間複雜度：O(m+n)，構建 LPS 表需要 O(n)，匹配過程需要 O(m)。
- 空間複雜度：O(n)，需要額外的 LPS 表。
總結
- 暴力解法簡單直接，但效率較低。
- KMP 演算法適合處理長字串匹配問題，其預處理的部分匹配表能有效避免重複計算。
希望這篇教學能幫助大家更理解 LeetCode 第 28 題的解法！