题解 | #正则表达式匹配#

二维动态规划。

def match(p, s):
    m, n = len(p), len(s)
    # 初始化边界：
    # 1、dp[0][0] = True，空模式空字符串，匹配成功；
    # 2、dp[0][j] = False，空模式无法匹配非空字符串；
    # 3、dp[i][0]不确定，只有模式为星号*时，才能匹配空字符串，即模式p前i个字符均为星号*。
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    for i in range(1, m + 1):
        if i == 1:
            dp[i][0] = p[i - 1] == "*"
        else:
            dp[i][0] = (p[i - 1] == "*") and dp[i - 2][0]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[i - 1] == "*":
                # 匹配*：若为.*，则匹配一切；若非.*，则ab*匹配a, ab, abb
                if p[i - 2] == ".":
                    dp[i][j] = True
                else:
                    dp[i][j] = (
                        dp[i - 2][j]
                        or dp[i - 1][j]
                        or (dp[i - 1][j - 1] and s[j - 2] == s[j - 1])
                    )
            elif p[i - 1] == "." and s[j - 1].isalnum():
                dp[i][j] = dp[i - 1][j - 1]
            elif s[j - 1].lower() == p[i - 1].lower():
                dp[i][j] = dp[i - 1][j - 1]
    return dp[m][n]


while True:
    try:
        string, pattern = input(), input()
        if match(pattern, string):
            print("true")
        else:
            print("false")
    except:
        break