10.md

题目地址

https://leetcode-cn.com/problems/regular-expression-matching/

解答

# 利用动态规划求解：
# 令dp[i][j]是s[0:i]和p[0:j]进行匹配，如果能匹配则为true，否则为false
# 动态规划状态方程式：
# 1 如果p[j] != '*'：
#  ]且(s[i] = p[j]或p[j] == '.')时，dp[i][j]为true，即
# dp[i][j] = i >= 1 and dp[i - 1][j - 1] and (s[i] == p[j] or p[j] == '.')
# 2 如果p[j] == '*':
# 1)p[j - 1]不用重复：
# dp[i][j] = dp[i][j - 2]
# 2)p[j - 1]至少重复一次：
# 当p[0:j]也能够匹配s[0:i - 1]，并且(s[i] = p[j - 1]或p[j - 2] = '.')时，dp[i][j]为true，即
# dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i] == p[j - 1] or p[j - 1] == '.'))
def isMatch(s, p):
    """ 正则表达式.和*匹配 """
    # 如果是空串则为“#”，若都为空串也可以进行比较
    s = '#' + s
    p = '#' + p
    lengs = len(s)
    lengp = len(p)
    dp = [[False for i in range(lengp)] for j in range(lengs)]
    dp[0][0] = True
    # 如果p空，s不空，则不可能匹配；如果s空而p不空，还是有可能可以匹配的,所以s要从空串开始进行
    for i in range(0, lengs):
        for j in range(1, lengp):
            if p[j] != '*':  # 如果不是“*”，则直接看对应的是否匹配,i=0是初始状态
                dp[i][j] = i >= 1 and dp[i - 1][j - 1] and (s[i] == p[j] or p[j] == '.')
            else:
                # 如果是“*”，则判断是否重复0次还是重复多次（如果重复多次的话，还保证p[0:j]和s[0:i - 1]也能够匹配）
                # i=0的时候主要是在这里生效
                dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i] == p[j - 1] or p[j - 1] == '.'))
    return dp[lengs - 1][lengp - 1]