[LeetCode解題攻略] 28. Find the Index of the First Occurrence in

題目描述

實作一個函數 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 中。

解題思路

要解決這個問題，我們需要從以下角度考慮：

1. 字串匹配：找到 needle 是否存在於 haystack 中。
2. 返回索引：如果匹配成功，返回第一個字符的索引；否則返回 -1。

我們可以從最簡單的暴力匹配到更高效的演算法（如 KMP 演算法）進行討論。

解法一：暴力解法

思路

使用兩層迴圈：

1. 外層迴圈遍歷 haystack 的每個字符作為起始位置。
2. 內層迴圈檢查從該起始位置開始的子字串是否與 needle 匹配。

詳細步驟

1. 檢查特殊情況：
2. • 如果 needle 是空字串，返回 0。
   • 如果 needle 長度大於 haystack，直接返回 -1。
2. 遍歷 haystack：
3. • 如果從當前索引開始的子字串與 needle 匹配，返回當前索引。
3. 如果遍歷結束仍無匹配，返回 -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 的每個字符之前的最長前綴後綴匹配長度。

步驟：

1. 初始化一個長度為 n 的數組 lps，所有值為 0。
2. 遍歷 needle，更新前綴後綴匹配長度。

詳細步驟

1. 構建 LPS 表。
2. 使用兩個指針進行匹配：
3. • 一個指向 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 題的解法！