題目鏈接
難度：困難 ??????類型：動態(tài)規(guī)劃

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

'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素

所謂匹配，是要涵蓋 整個 字符串 s的，而不是部分字符串。

示例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

解題思路

直接上動態(tài)方程：

1. p[j] == s[i]:dp[i][j] = dp[i-1][j-1]
2. p[j] == ".":dp[i][j] = dp[i-1][j-1]
3. p[j] =="*":
   3.1 p[j-1] != s[i]:dp[i][j] = dp[i][j-2]
   3.2 p[i-1] == s[i] or p[i-1] == ".":
   dp[i][j] = dp[i-1][j] // 匹配多個a
   or dp[i][j] = dp[i][j-1] // 匹配單個a
   or dp[i][j] = dp[i][j-2] // 匹配空字符

參考：https://leetcode-cn.com/problems/two-sum/solution/dong-tai-gui-hua-by-powcai/

代碼實現(xiàn)

class Solution:
    def isMatch(self, s, p):
      
        s_len = len(s)
        p_len = len(p)
        dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
        
        dp[0][0] = True
        for i in range(p_len):
            if p[i] == "*" and dp[0][i - 1]:
                dp[0][i + 1] = True
        
        for i in range(s_len):
            for j in range(p_len):
                if p[j] == s[i] or p[j] == ".":
                    dp[i + 1][j + 1] = dp[i][j]
                elif p[j] == "*":
                    if p[j - 1] != s[i]:
                        dp[i + 1][j + 1] = dp[i + 1][j - 1]
                    if p[j-1] == s[i] or p[j-1] == ".":
                        dp[i+1][j+1] = (dp[i][j+1] or dp[i+1][j]   or  dp[i+1][j-1])
        
        return dp[-1][-1]

本文鏈接：http://www.itdecent.cn/p/f1e0bac8e4d3