問題描述

輸入字符串 (s) 和模式 (p)，實現(xiàn)支持 '.' 和 '*' 的正則表達式。

'.' 能匹配任意單字符
'*' 能匹配 0 個或多個該符號前面的字符

匹配需覆蓋整個字符串 (而不是一部分)。

注意：

• s 為只包含 a-z 的字符串，且它可以為空
• p 為只包含 a-z、. 或 * 的字符串，且它可以為空

例 1:

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 不能匹配整個字符串 "aa"

例 2:

輸入:
s = "aa"
p = "a*"
輸出: true
解釋: '*' 意味著 0 到多個前置元素 - 'a'。 因此，將 'a' 重復 1 次，即 "aa"。

例 3:

輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 意為著 "0 個或多個 (*) 任意的字符 (.)"。

例 4:

輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: "c*" 可以表示將 c 重復 0 次，a 可以重復 1 次，因此得到 "aab"。

例 5:

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

問題難度

Hard

解題思路

本題是名副其實的 Hard，因為沒有特別好的思路，我也是求助于 Solution，下面會描述 Solution 中的 2 種解題思路：

方法 1：遞歸法

這題難在 * 符號的處理上，如果沒有該符號，程序會簡單很多，你只需要遞歸匹配每個字符即可，如下：

# 無 * 的情況
class Solution(object):
    def isMatch(self, s, p):
        if not p: return not s

        firstMatch = True if s and p[0] in {s[0], '.'} else False
        return firstMatch and self.isMatch(s[1:], p[1:])

增加了 * 的支持后，該符號會增加兩種操作：

1. 如 s 當前字符與 * 前面的字符不匹配，則刪除 p 中的 * 及其前面的 1 個字符，例如上面 例 4 中的 c*
2. 否則刪除 s 中與 * 之前字符相匹配的 1 個字符

為了涵蓋這 2 種操作，以上代碼可改為：

class Solution(object):
    def isMatch(self, s, p):
        if not p: return not s

        firstMatch = True if s and p[0] in {s[0], '.'} else False
        
        if len(p) > 1 and p[1] == "*":
            # 對 * 處理的 2 種操作
            return firstMatch and self.isMatch(s[1:], p) or self.isMatch(s, p[2:])
        else:        
            return firstMatch and self.isMatch(s[1:], p[1:])    

方法 2：動態(tài)規(guī)劃

保留方法 1 的思路，同時利用動態(tài)規(guī)劃的思想，把 s 和 p 匹配過的結果緩存下來，這樣當重復的 s[i:] 和 p[j:] 出現(xiàn)時，可以直接從緩存中讀取，減少重復計算的開銷：

class Solution(object):
    def isMatch(self, s, p):
        mem = {}
        def dp(i, j):
            if (i, j) in mem:
                return mem[(i, j)]

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

            mem[(i, j)] = res
            return res
        return dp(0, 0)

原題鏈接