10. 正则表达式匹配-leetCode&python

1、题目
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

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

2、代码

class Solution(object):

        def isMatch(self, s, p):
            """
            使用一个二维数组dp来记录字符串s的前i个字符和模式p的前j个字符是否匹配。然后根据字符规律p中的字符进行状态转移，最终返回dp[m][n]，表示整个字符串s和模式p是否匹配，其中m为字符串s的长度，n为字符规律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]
            # 状态更新
            """
            遍历字符串s和模式p的所有字符，根据当前字符的匹配情况进行状态更新。
            如果当前字符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]为'*'，则需要进一步判断：
            如果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]可以从两种状态转移而来：要么''表示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)