這篇文章將介紹 LeetCode 題目 10. Regular Expression Matching，這是一道有趣且具有挑戰性的動態規劃題目，涉及實現一個正則表達式匹配算法。這道題目主要考察對正則表達式中的特殊字符 . 和 * 的理解和處理，並運用動態規劃進行高效求解。
題目概述
給定一個字串 s 和一個正則表達式模式 p，實現一個函數來判斷 p 是否能匹配 s 的完整字串。p 包含兩種特殊字符：
.：匹配任何單一字符。*：匹配零個或多個前面的那個元素。
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]。
- 基礎條件：
dp[0][0] = True，空字串與空模式是匹配的。- 當模式
p中包含*時，*可以消去之前的字符，因此需要初始化dp[0][j]的值，若模式是a*,a*b*這類形式。
- 遞推關係：
- 當
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 的動態規劃解法！
