正则表达式匹配

题目：
给定一个字符串 (s) 和一个字符模式 §。实现支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符。
'’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 。
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
思想：
#str从i位置和exp从j位置的之后的是否能匹配
#看j+1位置
#（1）无j+1
#（2）不是“”，i和j配不上一定返回FALSE，否则递归判断下一个位置
#（3）是“*”，【i=j和i!=j两种情况】递归

递归：

#str从i位置和exp从j位置的之后的是否能匹配
class Solution:
    def isMatch(self, s: str, p: str) -> bool:       
        
        def process(str,exp,i,j):
            if j==len(exp):    #exp到最后
                    return i==len(str)
            if j==len(exp)-1 or exp[j+1]!="*": #情况1和情况2
                    return i!=len(str) and (exp[j]==str[i] or exp[j]==".") and process(str,exp,i+1,j+1)
            while i!=len(str) and (exp[j]==str[i] or exp[j]=="."):  #j+1是“*”
                    if process(str,exp,i,j+2):
                        return True
                    i+=1
            return process(str,exp,i,j+2)
        return process(s,p,0,0)

动态规划：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def dp_boohave(str, exp):
            dp = intidp(str, exp)
            for i in range(len(str) - 1, -1, -1):
                for j in range(len(exp) - 2, -1, -1):
                    if exp[j + 1] != "*":
                        dp[i][j] = (str[i] == exp[j] or exp[j] == ".") and dp[i + 1][j + 1]
                    else:
                        si = i
                        while si != len(str) and (str[si] == exp[j] or exp[j] == "."):
                            if dp[si][j + 2]:
                                dp[i][j] = True
                                break
                            si += 1
                        if dp[i][j] != True:
                            dp[i][j] = dp[si][j + 2]
            return dp

        def intidp(s, e):
            slen = len(s)
            elen = len(e)
            dp = [[False] * (elen + 1) for i in range(slen + 1)]
            dp[slen][elen] = True
            for j in range(elen - 2, -1, -2):
                if e[j] != "*" and e[j + 1] == "*":
                    dp[slen][j] = True
                else:
                    break
            if slen > 0 and elen > 0:
                if e[elen - 1] == "." or e[elen-1] == s[slen - 1]:
                    dp[slen-1][elen-1]=True
            return dp
        return dp_boohave(s, p)[0][0]