Python 算法学习-动态规划-正则表达式

0821fzh

# 给定一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配
# '.' 匹配任意单个字符
# '*' 匹配零个或多个前面的那一个元素
def is_match(s: str, p: str):
    def matches(i, j):

        # 没有字符，匹配失败
        if i == 0:
            return False

        # .匹配任意字符
        if p[j - 1] == '.':
            return True

        return s[i - 1] == p[j - 1]
    m, n = len(s), len(p)
    # dp[j]: s的前i个字符与p的前j个字符是否能匹配
    dp = [[False] * (n + 1) for _ in range(m + 1)]

    # base case
    # 空白匹配空白
    dp[0][0] = True

    for i in range(m + 1):
        for j in range(1, n + 1):

            # 匹配'*'通配符有两种情况:
            # 1.要么匹配0次,匹配j前进2位再进行判断
            # 2.要么进行匹配，字符i前进1位,再进行匹配
            if p[j - 1] == '*':
                dp[j] |= dp[j - 2]  # 0次匹配, 跳过
                dp[j] |= dp[i - 1][j] and matches(i, j - 1)  # 匹配*号前的字符，字符串前进一位
            else:
                # 判断前个匹配情况和当前匹配情况
                dp[j] = dp[i - 1][j - 1] and matches(i, j)

    return dp[m][n]


# 测试代码
s = 'aabb'
p = 'a*.b'
print(is_match(s, p))