LeetCode 10. 正則表達式匹配

10. 正則表達式匹配

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

題目

給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達式匹配结闸。

'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配桦锄，是要涵蓋整個字符串 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

解題思路

暴力解

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

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

如果只是要求檢查兩個普通字符是否匹配魁瞪。那么通過直接遍歷诅迷，檢查每個數(shù)組對應的元素是否相同來判斷是否匹配即可众旗。例如：

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:])

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

現(xiàn)在來處理兩個符號的問題而叼，. 這個符號，表示的是匹配處換行符以外的任意字符（這里就不展開說明了葵陵，若需詳細了解，可直接上網(wǎng)搜索）娇钱。

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

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 中的元素可能出現(xiàn)固定字符姨裸，或者 . 號怨酝，所以當 p 出現(xiàn)的字符與 s 中對應的字符相同，或者 p 此處是 . 字符农猬，這里兩者都表示能夠匹配。

那么現(xiàn)在往下看 * 符號慷垮，這個符號表示的含義是重復零次或多次。那么這里最明顯的字符就是重復多少次的問題汤纸？在這里考慮使用遞歸的方式書寫芹血，假設重復 n 次，其實這里先不需要考慮 n 是多少幔烛，把這個交給遞歸實現(xiàn)。要考慮那么當下的情況议惰，這里應該就只有兩個選擇乡恕，要么是匹配 0 次，要么是匹配 1 次傲宜。

那么相應的代碼就應該修改為（這里書寫發(fā)現(xiàn) * 的情況）：

# 這里表示發(fā)現(xiàn) `*` 的情況下，
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 中字符與 * 結(jié)合這部分豺总。后面的表示，p[0] 和 s[0] 匹配之后另玖，繼續(xù)判斷 s 接下來的元素。其中保留 p日矫，只向后移動 s绑榴，是為了實現(xiàn) * 匹配多次的功能翔怎。

這樣來看，其實已經(jīng)可以說理清兩個符號的具體實現(xiàn)方式赤套。

關于完整的代碼請查看【代碼實現(xiàn)】部分。

動態(tài)規(guī)劃

思路：動態(tài)規(guī)劃

在上面暴力解的方法中宣脉，頻繁使用切片操作剔氏，復雜度高。這里在暴力解的基礎上谈跛，使用動態(tài)規(guī)劃的方法，定義變量 i蜡励，j 來記錄當前匹配到的位置阻桅，用 dp(i, j) 表示 s[i:] 和 p[j:] 是否能夠匹配。占遥，避免頻繁切片输瓜。這里也引入備忘錄的概念，用來避免重復的運算尤揣。

具體代碼同樣請查看【代碼實現(xiàn)】部分。

代碼實現(xiàn)

暴力解 | 代碼實現(xiàn)

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:])

動態(tài)規(guī)劃 | 代碼實現(xiàn)

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)

實現(xiàn)結(jié)果

暴力解 | 實現(xiàn)結(jié)果

動態(tài)規(guī)劃 | 實現(xiàn)結(jié)果

以上就是使用暴力解的形式，理清題目的難點旧蛾，進而使用動態(tài)規(guī)劃加備忘錄的形式來進一步降低復雜度，更高效的解決《10. 正則表達式匹配》問題的主要內(nèi)容毯盈。

歡迎關注微信公眾號《書所集錄》

LeetCode 10. 正則表達式匹配 | Python