LeetCode Prob.10 Regular Expression Matching

动规就完事了。

首先，我们得想到，由于letter + *结构允许0和多个字符存在，所以处理的时候，应该把它们看作一体，也就是说，除了当前字符，每时每刻都要考虑下一个字符是不是*。

而且，考虑一下两个字符串在空的时候有什么行为：

• s空了，没关系，p可能有*表达式帮助匹配。
• p空了，必须看s有没有空。

所以，我们必须先进行p的空检测

最后，考虑状态转移：

• 对于*模式：
  • 零宽匹配， dp(i, j+2)。
  • 有字符可匹配， first_matched and dp(i + 1, j)，下一个状态中依然会进行*模式的判断。
• 对于非*模式：
  • s空的时候，那么肯定就匹配失败了。
  • 否则，first_matched and dp(i + 1, j + 1)。

在实现的时候，s空可以在状态转移之前，通过first_matched赋值的方式进行处理。

然后就是逻辑细节了：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        d = {}
        def dp(spt, ppt):
            if (spt, ppt) not in d:
                # 判断p空
                if ppt == len(p):
                    ans = spt == len(s)
                else:
                    # 判断第一个字符是否匹配或者s空
                    fm = spt < len(s) and p[ppt] in {s[spt], '.'}
                    # 对*模式的处理
                    if ppt + 1 < len(p) and p[ppt + 1] == '*':
                        ans = dp(spt, ppt + 2) or fm and dp(spt + 1, ppt)
                    # 对非*模式的处理
                    else:
                        ans = dp(spt + 1, ppt + 1) and fm 
                # 写入字典
                d[spt, ppt] = ans
            return d[spt, ppt]
        return dp(0, 0)