LeetCode 10. 正則運算式匹配

10. 正則運算式匹配

題目來源：https://leetcode-cn.com/problems/regular-expression-matching

題目

給你一個字串 s 和一個字符規律 p，請你來實作一個支持 '.' 和 '*' 的正則運算式匹配，

'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋整個字串 s的，而不是部分字串，

說明:

s 可能為空，且只包含從 a-z 的小寫字母，
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *，

示例 1:

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字串，

示例 2:

輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'，因此，字串 "aa" 可被視為 'a' 重復了一次，

示例 3:

輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個或多個（'*'）任意字符（'.'），

示例 4:

輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因為 '*' 表示零個或多個，這里 'c' 為 0 個, 'a' 被重復一次，因此可以匹配字串 "aab"，

示例 5:

輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false

解題思路

暴力解

先從【暴力解】的角度理清問題，

這個題目中，難點就在于處理 . 和 * 兩個符號，

如果只是要求檢查兩個普通字符是否匹配，那么通過直接遍歷，檢查每個陣列對應的元素是否相同來判斷是否匹配即可，例如：

def isMatch(s, p):
    if len(s) != len(p):
        return False
    for i in range(p):
        if s[i] != p[i]:
            return False
    return True

那代碼大概就會是這樣，那我們用遞回的形式來書寫，以下為偽代碼：

def isMatch(s, p):
    """
    s: text
    p: pattern
    """
    if p is empty:
        return s is empty
    first_match = (s not empty) and p[0] == s[0]
    return first_match and isMatch(s[1:], p[1:])

在上面的代碼中，其實就是通過先判斷前面的元素是否匹配，逐層往下判斷后面的元素是否也匹配，從而來找到答案，

現在來處理兩個符號的問題，. 這個符號，表示的是匹配處換行符以外的任意字符（這里就不展開說明了，若需詳細了解，可直接上網搜索），

了解這個符號的含義后，這里所能表達的意義，也會相應的改變，即是說，當 p 中出現 . 號，s 對應的元素無論是什么字符（題目說明 s 僅包含 a-z 字符）都能夠匹配，現在根據上面的偽代碼進行修改：

def isMatch(s, p):
    """
    s: text
    p: pattern
    """
    if not p:
        return not s
    first_match = bool(s) and p[0] in {s[0], '.'}
    return first_match and isMatch(s[1:], p[1:])

這里唯一不同的就是 first_match 這部分的判斷中，因為 p 中的元素可能出現固定字符，或者 . 號，所以當 p 出現的字符與 s 中對應的字符相同，或者 p 此處是 . 字符，這里兩者都表示能夠匹配，

那么現在往下看 * 符號，這個符號表示的含義是重復零次或多次，那么這里最明顯的字符就是重復多少次的問題？在這里考慮使用遞回的方式書寫，假設重復 n 次，其實這里先不需要考慮 n 是多少，把這個交給遞回實作，要考慮那么當下的情況，這里應該就只有兩個選擇，要么是匹配 0 次，要么是匹配 1 次，

那么相應的代碼就應該修改為（這里書寫發現 * 的情況）：

# 這里表示發現 `*` 的情況下，
if len(p) >= 2 and p[1] == '*':
    # 這里需要考慮匹配 0 次的問題，例如 aa，c*aa
    # 也要考慮匹配多次的問題，例如 aa, a*
    return isMatch(s, p[2:]) or first_match and isMatch(s[1:], p)

在這段代碼當中，isMatch(s, p[2:]) 這里表示，字符匹配 0 次，跳過 p 中字符與 * 結合這部分，后面的表示，p[0] 和 s[0] 匹配之后，繼續判斷 s 接下來的元素，其中保留 p，只向后移動 s，是為了實作 * 匹配多次的功能，

這樣來看，其實已經可以說理清兩個符號的具體實作方式，

關于完整的代碼請查看【代碼實作】部分，

動態規劃

思路：動態規劃

在上面暴力解的方法中，頻繁使用切片操作，復雜度高，這里在暴力解的基礎上，使用動態規劃的方法，定義變數 i，j 來記錄當前匹配到的位置，用 dp(i, j) 表示 s[i:] 和 p[j:] 是否能夠匹配，，避免頻繁切片，這里也引入備忘錄的概念，用來避免重復的運算，

具體代碼同樣請查看【代碼實作】部分，

代碼實作

暴力解 | 代碼實作

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s

        first_match = bool(s) and p[0] in {s[0], '.'}

        if len(p) >= 2 and p[1]=="*":
            return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
        else:
            return first_match and self.isMatch(s[1:], p[1:])

動態規劃 | 代碼實作

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(p):
                    return i == len(s)

                else:
                    first_match = i < len(s) and p[j] in {s[i], '.'}
                    if j + 1 < len(p) and p[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[(i, j)] = ans

            return memo[(i, j)]

        return dp(0, 0)