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

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

2、代碼

class Solution(object):

        def isMatch(self, s, p):
            """
            使用一個二維數(shù)組dp來記錄字符串s的前i個字符和模式p的前j個字符是否匹配。然后根據(jù)字符規(guī)律p中的字符進(jìn)行狀態(tài)轉(zhuǎn)移，最終返回dp[m][n]，表示整個字符串s和模式p是否匹配，其中m為字符串s的長度，n為字符規(guī)律p的長度。
            """
            len_s, len_p = len(s), len(p)
            dp = [[False] * (len_p + 1) for _ in range(len_s + 1)]  # 字符串s的前i個字符和模式p的前j個字符是否匹配。

            # 初始化
            dp[0][0] = True
            for j in range(1, len_p + 1):
                if p[j - 1] == '*':
                    dp[0][j] = dp[0][j - 2]
            # 狀態(tài)更新
            """
            遍歷字符串s和模式p的所有字符，根據(jù)當(dāng)前字符的匹配情況進(jìn)行狀態(tài)更新。
            如果當(dāng)前字符s[i - 1]和p[j - 1]相等，或者p[j - 1]為'.'，則dp[i][j]取決于dp[i - 1][j - 1]，即s的前i-1個字符和p的前j-1個字符是否匹配。
            如果p[j - 1]為'*'，則需要進(jìn)一步判斷：
            如果s[i - 1]和p[j - 2]不相等，并且p[j - 2]也不是'.'，則'*'表示0個前面的字符，此時dp[i][j]取決于dp[i][j - 2]。
            否則，''可以表示0個或多個前面的字符。如果s[i - 1]和p[j - 2]相等，或者p[j - 2]為'.'，則dp[i][j]可以從兩種狀態(tài)轉(zhuǎn)移而來：要么''表示0個前面的字符（dp[i][j - 2]），要么'*'表示多個前面的字符（dp[i - 1][j]）。
            """
            for i in range(1, len_s + 1):
                for j in range(1, len_p + 1):
                    if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                        dp[i][j] = dp[i - 1][j - 1]
                    elif p[j - 1] == '*':
                        if s[i - 1] != p[j - 2] and p[j - 2] != '.':
                            dp[i][j] = dp[i][j - 2]
                        else:
                            dp[i][j] = dp[i][j - 2] | dp[i - 1][j]
            return dp[len_s][len_p]

3、示例

    s=Solution()
    ts='aab'
    p='.*'
    res=s.isMatch(ts,p)
    print(res)