Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：28 .Find the Index of the First Occurrence in a String（找出字符串中第一個匹配項的下標）

從暴力法到 KMP 演算法，深入理解字符串匹配的精髓

luk 收錄於 Leetcode
 約 1100 字 預計閱讀 5 分鐘 

題目描述

給定兩個字符串 haystack 和 needle，請你在 haystack 字符串中找出 needle 字符串的第一個匹配項的下標（下標從 0 開始）。如果 needle 不是 haystack 的一部分，請返回 -1。

範例

範例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標 0 和 6 處出現。
第一個匹配項在下標 0 處，所以返回 0。

範例 2：

輸入：haystack = "leetcode", needle = "leeto"
輸出：-1
解釋："leeto" 沒有在 "leetcode" 中出現，所以返回 -1。

限制條件

  • 1 <= haystack.length, needle.length <= 10^4
  • haystack 和 needle 僅由小寫英文字符組成

核心概念理解

1. 問題本質

這是經典的字符串匹配問題（String Matching Problem）：

  • 在主字符串（haystack）中尋找子字符串（needle）
  • 返回第一次出現的位置
  • 如果找不到返回 -1

2. 實際應用場景

這個問題在實際開發中非常常見：

  • 文本編輯器的「尋找」功能
  • 網頁搜索中的關鍵字匹配
  • 編譯器中的模式識別
  • 生物資訊學中的 DNA 序列匹配

解法一：內建函數法（最簡單）

思路

Python 提供了內建的字符串方法 find() 和 index()，可以直接使用。

程式碼實現 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # 使用內建 find 方法
        return haystack.find(needle)
        
        # 或者手動處理
        # if needle in haystack:
        #     return haystack.index(needle)
        # return -1

複雜度分析

  • 時間複雜度：O(n×m)，其中 n 是 haystack 長度，m 是 needle 長度
  • 空間複雜度：O(1)

解法二：暴力匹配法（基礎解法）

思路

逐個位置嘗試匹配：

  1. 從 haystack 的每個位置開始
  2. 檢查是否能完整匹配 needle
  3. 找到就返回起始位置

程式碼實現 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)
        
        # 遍歷所有可能的起始位置
        for i in range(n - m + 1):
            # 檢查從位置 i 開始是否匹配
            match = True
            for j in range(m):
                if haystack[i + j] != needle[j]:
                    match = False
                    break
            
            if match:
                return i
        
        return -1

優化版本（使用切片） 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)
        
        # 使用切片比較，更 Pythonic
        for i in range(n - m + 1):
            if haystack[i:i+m] == needle:
                return i
        
        return -1

執行過程視覺化 

haystack = "sadbutsad", needle = "sad"

位置 0：
sadbutsad
sad
^^^  匹配成功！返回 0

範例 2：haystack = "leetcode", needle = "leeto"

位置 0：
leetcode
leeto
^^^^× 第 5 個字符不匹配

位置 1：
leetcode
 leeto
 ×     第 1 個字符就不匹配

... 繼續嘗試所有位置，都失敗
返回 -1

複雜度分析

  • 時間複雜度：O(n×m)，最壞情況下需要檢查每個位置的每個字符
  • 空間複雜度：O(1)

解法三：滑動窗口優化

思路

使用滑動窗口的概念，但加入一些優化：

  1. 當發現不匹配時，可以跳過一些明顯不可能的位置
  2. 利用已經比較過的信息

程式碼實現 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(haystack)
        m = len(needle)
        
        i = 0
        while i <= n - m:
            # 先比較第一個字符
            if haystack[i] == needle[0]:
                # 如果第一個字符匹配，再比較其餘部分
                j = 1
                while j < m and haystack[i + j] == needle[j]:
                    j += 1
                
                if j == m:
                    return i
            
            i += 1
        
        return -1

解法四：雙指針法

思路

使用兩個指針分別追蹤 haystack 和 needle 的當前位置。

程式碼實現 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        i = 0  # haystack 指針
        j = 0  # needle 指針
        
        while i < len(haystack) and j < len(needle):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                # 回溯到下一個可能的起始位置
                i = i - j + 1
                j = 0
        
        # 檢查是否完全匹配
        if j == len(needle):
            return i - j
        else:
            return -1

解法五：KMP 演算法（進階解法）

思路

KMP（Knuth-Morris-Pratt）演算法通過預處理 needle，建立一個「部分匹配表」（也叫 failure function），避免重複比較。

核心概念：前綴後綴匹配 

對於字符串 "ABCDABD"：
- 前綴：A, AB, ABC, ABCD, ABCDA, ABCDAB
- 後綴：D, BD, ABD, DABD, CDABD, BCDABD

部分匹配值 = 最長的相同前綴後綴的長度

程式碼實現 

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        
        # 建立部分匹配表
        lps = self.computeLPS(needle)
        
        i = 0  # haystack 指針
        j = 0  # needle 指針
        
        while i < len(haystack):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
                
                if j == len(needle):
                    return i - j
            else:
                if j != 0:
                    # 利用部分匹配表跳轉
                    j = lps[j - 1]
                else:
                    i += 1
        
        return -1
    
    def computeLPS(self, pattern: str) -> List[int]:
        """計算部分匹配表（最長前綴後綴）"""
        m = len(pattern)
        lps = [0] * m
        length = 0  # 最長前綴後綴的長度
        i = 1
        
        while i < m:
            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

KMP 演算法視覺化 

haystack = "ABABDABACDABABCABAB"
needle = "ABABCABAB"

第一步：建立 LPS 表
needle:   A B A B C A B A B
lps:      0 0 1 2 0 1 2 3 4

第二步：匹配過程
ABABDABACDABABCABAB
ABABCABAB
^^^^×     在位置 4 失敗

利用 LPS，j 跳到 lps[3] = 2
ABABDABACDABABCABAB
  ABABCABAB
  ××       快速跳過

繼續匹配...
最終在位置 10 找到完整匹配

複雜度分析

  • 時間複雜度：O(n + m)，線性時間
  • 空間複雜度：O(m)，用於存儲 LPS 表

解法比較

解法時間複雜度空間複雜度優點缺點
內建函數O(n×m)O(1)簡單直接面試時可能不被接受
暴力法O(n×m)O(1)容易理解和實現效率較低
滑動窗口O(n×m)O(1)有一定優化最壞情況仍是 O(n×m)
KMPO(n+m)O(m)時間複雜度最優實現複雜，理解困難

常見錯誤與陷阱

錯誤 1：邊界條件處理不當 

# ❌ 錯誤：沒有考慮 needle 為空的情況
def strStr(self, haystack: str, needle: str) -> int:
    for i in range(len(haystack) - len(needle) + 1):
        if haystack[i:i+len(needle)] == needle:
            return i
    return -1

# ✅ 正確：處理邊界情況
def strStr(self, haystack: str, needle: str) -> int:
    if not needle:  # 空字符串應該返回 0
        return 0
    # ... 其餘邏輯

錯誤 2：索引越界 

# ❌ 錯誤：可能越界
def strStr(self, haystack: str, needle: str) -> int:
    for i in range(len(haystack)):  # 應該是 len(haystack) - len(needle) + 1
        if haystack[i:i+len(needle)] == needle:
            return i
    return -1

錯誤 3：KMP 實現錯誤 

# ❌ 錯誤：LPS 計算錯誤
def computeLPS(self, pattern: str) -> List[int]:
    lps = [0] * len(pattern)
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[0]:
            lps[i] = 1  # 錯誤！沒有考慮更長的匹配
    return lps

進階思考

1. 如果要找所有出現位置？ 

def findAllOccurrences(haystack: str, needle: str) -> List[int]:
    """返回所有匹配位置"""
    positions = []
    start = 0
    
    while True:
        pos = haystack.find(needle, start)
        if pos == -1:
            break
        positions.append(pos)
        start = pos + 1  # 從下一個位置繼續尋找
    
    return positions

2. 如果要忽略大小寫？ 

def strStrIgnoreCase(haystack: str, needle: str) -> int:
    """忽略大小寫的匹配"""
    return haystack.lower().find(needle.lower())

3. 如果要支持通配符？ 

def strStrWithWildcard(haystack: str, pattern: str) -> int:
    """支持 '?' 作為單字符通配符"""
    n, m = len(haystack), len(pattern)
    
    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if pattern[j] != '?' and haystack[i + j] != pattern[j]:
                match = False
                break
        if match:
            return i
    
    return -1

效能優化技巧

1. 字符頻率優化 

def strStrOptimized(haystack: str, needle: str) -> int:
    # 先檢查 needle 中的字符是否都在 haystack 中
    needle_chars = set(needle)
    haystack_chars = set(haystack)
    
    if not needle_chars.issubset(haystack_chars):
        return -1
    
    # 繼續正常匹配...
    return haystack.find(needle)

2. Boyer-Moore 思想 

def strStrBM(haystack: str, needle: str) -> int:
    """簡化版 Boyer-Moore，從後往前匹配"""
    n, m = len(haystack), len(needle)
    
    i = m - 1
    while i < n:
        j = m - 1
        k = i
        
        while j >= 0 and haystack[k] == needle[j]:
            j -= 1
            k -= 1
        
        if j < 0:
            return k + 1
        
        # 簡單跳轉策略
        i += max(1, j)
    
    return -1

測試案例 

def test_strStr():
    test_cases = [
        # (haystack, needle, expected)
        ("sadbutsad", "sad", 0),
        ("leetcode", "leeto", -1),
        ("hello", "ll", 2),
        ("aaaaa", "bba", -1),
        ("", "", 0),
        ("a", "", 0),
        ("", "a", -1),
        ("mississippi", "issip", 4),
        ("aabaaabaaac", "aabaaac", 4),
        ("ababcababa", "ababa", 5),
    ]
    
    solution = Solution()
    for haystack, needle, expected in test_cases:
        result = solution.strStr(haystack, needle)
        assert result == expected, f"Failed: {haystack}, {needle}"
        print(f"✅ 通過：在 '{haystack}' 中尋找 '{needle}' → {result}")

相關題目

  1. LeetCode 214: Shortest Palindrome
  2. LeetCode 459: Repeated Substring Pattern
  3. LeetCode 686: Repeated String Match
  4. LeetCode 796: Rotate String

總結

這道題展示了字符串匹配的多種解法：

  1. 基礎方法足夠用：對於 LeetCode 的測試用例，暴力法已經足夠
  2. 理解 KMP 的價值：雖然實現複雜，但展示了演算法優化的思想
  3. 實際應用考量：根據具體場景選擇合適的方法
  4. 掌握內建函數：實際開發中，使用內建函數是最實用的

記住：先實現正確的解法，再考慮優化！

練習建議

  1. 先實現暴力法，確保理解基本邏輯
  2. 嘗試手動模擬 KMP 演算法的執行過程
  3. 研究其他字符串匹配演算法（如 Rabin-Karp）
  4. 練習相關的字符串處理題目
  5. 在不同程式語言中實現，體會差異
更新於 2024-12-24 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmStringPattern-Matching
返回 | 主頁
0%