[LeetCode解題攻略] 10. Regular Expression Matching

這篇文章將介紹 LeetCode 題目 10. Regular Expression Matching，這是一道有趣且具有挑戰性的動態規劃題目，涉及實現一個正則表達式匹配算法。這道題目主要考察對正則表達式中的特殊字符 . 和 * 的理解和處理，並運用動態規劃進行高效求解。

題目概述

給定一個字串 s 和一個正則表達式模式 p，實現一個函數來判斷 p 是否能匹配 s 的完整字串。p 包含兩種特殊字符：

1. .：匹配任何單一字符。
2. *：匹配零個或多個前面的那個元素。

範例：

Input: s = "aa", p = "a"
Output: false

Input: s = "aa", p = "a*"
Output: true

Input: s = "ab", p = ".*"
Output: true

Input: s = "aab", p = "c*a*b"
Output: true

Input: s = "mississippi", p = "mis*is*p*."
Output: false

思路分析

這道題目主要的挑戰在於處理 * 的匹配。通過 *，模式中一個字符可以出現零次或多次，而 . 可以匹配任何字符。因此，我們可以將此題轉化為一個動態規劃問題來處理。

動態規劃定義

我們使用一個布爾值二維數組 dp[i][j]，表示 s[0:i] 是否能夠匹配 p[0:j]。

1. 基礎條件：
2. • dp[0][0] = True，空字串與空模式是匹配的。
   • 當模式 p 中包含 * 時，* 可以消去之前的字符，因此需要初始化 dp[0][j] 的值，若模式是 a*, a*b* 這類形式。
2. 遞推關係：
3. • 當 p[j-1] 是普通字符或 . 時，匹配情況取決於 dp[i-1][j-1] 和當前字符是否相同。
   • 當 p[j-1] 是 * 時，有兩種情況：
   • • 不使用 *，即 dp[i][j] = dp[i][j-2]。
     • 使用 *，即 dp[i][j] = dp[i-1][j]，且 s[i-1] 必須等於 p[j-2] 或 p[j-2] 是 .。

解法：動態規劃

根據上述思路，我們可以逐步構建 dp 表來得到最終匹配結果。

實作 (Python)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        
        # 初始化：空字串和空模式匹配
        dp[0][0] = True
        
        # 初始化模式中 `*` 的情況
        for j in range(2, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        
        # 填充 DP 表
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    # 匹配零次或多次前一個字符
                    dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))
                else:
                    # 匹配單一字符
                    dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '.')
        
        return dp[m][n]

複雜度分析

• 時間複雜度：O(m * n)，其中 m 和 n 分別是字串 s 和模式 p 的長度。我們需要填充整個 dp 表。
• 空間複雜度：O(m * n)，同樣需要 dp 表來存儲每個子問題的解。

總結

這道題目通過使用動態規劃進行解決，具體解法包括：

• 使用二維動態規劃表 dp[i][j] 來存儲 s[0:i] 和 p[0:j] 是否匹配的結果。
• 處理正則表達式中的 * 和 . 特殊字符。
• 遞推地構建整個匹配過程並考慮所有邊界情況。

希望這篇教學能幫助你掌握 Regular Expression Matching 的動態規劃解法！