[数据结构与算法]LeetCode10-正则表达式匹配（递归）

观前提示1：全文6600+字，文章较长，讲解了递归的一般思路，耐心看完，相信你一定有所收获

观前提示2：本文的解法效率并不高，只是代码思路较为清晰，分享的是思想而非解法

题目背景

给你一个字符串?s?和一个字符规律?p，请你来实现一个支持?'.'?和?'*'?的正则表达式匹配。

• '.'?匹配任意单个字符
• '*'?匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个?字符串?s的，而不是部分字符串。

编程前

一道典型的动态规划或者递归的算法题，难度是hard，无论是dp还是递归，思路都差不多：找到转移方程（是的，递归也需要找转移方程，如何降到小规模的问题），本文章采取递归的方法，为了避免堆栈溢出，加了cache

编程中

编程伊始：边界检查

一开始比较简单，做条件判断和边界检查

class Solution:
    cache = {}    
    def isMatch(self, s: str, p: str) -> bool:
        ############### 边界检查部分Start ###############
        if p == "":
            Solution.cache[(s,p)] = s==""
            return s==""
        if s == "":
            if p == "":
                Solution.cache[(s,p)]=True
                return True
        if p == s:
            Solution.cache[(s,p)]=True
            return True
        ############### 边界检查部分End ###############

需要注意的是，当s为空的时候，p可以是空，也可以是任意字符和*的组合，其实 【任意字符和*的组合可以匹配空】这件事是很容易被忽略的

编程核心：转移方程

递归里面也有类似转移方程的概念，一个大规模的问题，想用一个小规模的问题去解，该怎么办呢，就需要找到小规模问题和大规模问题之间的联系，这种联系在动态规划里面就是转移方程，因为这里涉及两个变量，所以很明显，这里的【小规模】也有很多种【解释】（至少需要两种解释）

• if?self.isMatch(s[:-1],?p[:-1])

• if self.isMatch(s[:-1],?p)

因为我们的【边界条件】是相等，或者一种为空，或者另一种为空，总共三种情况，又因为在递归的场景下，需要让情况【坍缩】到某一个【边界条件】中，所以在找【小规模问题】的时候，就必须使得：

• 让其中一个变量为空
• 让s和p相等（这个条件用处不大）

最好的情况一般是(s[:-1], p) 和(s, p[:-1])，但往往这种组合在题目中没有实际意义，或者无法覆盖全部情况。所以第一步我就找到了这两种的组合（有没有其他找【小规模问题】的方法呢，这里挖一个坑，在文章的【总结】部分解决，不过瘾的同学也可以直接去【总结】看答案，但是强烈建议大家跟着文章的思路走）此时代码如下（注意用到了范围，就一定要判断长度是否够）

class Solution:
    cache = {}
    def isMatch(self, s: str, p: str) -> bool:
        ############### 边界检查部分Start ###############
        if p == "":
            Solution.cache[(s,p)] = s==""
            return s==""
        if s == "":
            if p == "":
                Solution.cache[(s,p)]=True
                return True
        if p == s:
            Solution.cache[(s,p)]=True
            return True
        ############### 边界检查部分End ###############
        if (s,p) in Solution.cache:
            return Solution.cache[(s,p)]
        ############### 小规模的问题Start ###############
        if len(s)>=1 and len(p)>=1 and self.isMatch(s[:-1], p[:-1]):
            pass
        if len(s)>=1 and self.isMatch(s[:-1], p):
            pass
        ############### 小规模的问题End ###############
        Solution.cache[(s,p)]=False
        return False

编程完善：分类讨论

如果是第一种情况：self.isMatch(s[:-1],?p[:-1])，意味着在已经match的情况下，s和p都要再加一个字符，很容易想到两种可能

• 两个字符相等
• p追加的字符是"."

此时有个问题，如果p追加的字符是"*"，有没有可能让这种情况成立呢？这里再挖一个坑，同样在总结的时候说，不过瘾的同学，可以直接跳到【总结】）。

如果是第二种情况：self.isMatch(s[:-1],?p)，意味着在已经match的情况下，s要再加一个字符，这时p很不爽，如果只有s强行追加，p的最后就一定是一个超能力的字符来兜底，就是"*"，因为"."是没有能力延长匹配的，然而字符"*"相当于一个辅助的字符，能否帮上忙完全看前面的字符，所以就要求"*"前面的字符给力一点，

• 如果前一个字符是"."，万事大吉
• 如果前一个字符是普通字符，那么就要求新加的字符也得是普通字符

将第二种情况的分析总结起来就是：

p的最后一个字符是"*"

p的倒数第二个字符能够匹配最后一个字符

此时代码如下，注意在用到下标的时候，一定要判断越界的情况

class Solution:
    cache = {}
    def isMatch(self, s: str, p: str) -> bool:
        ############### 边界检查部分Start ###############
        if p == "":
            Solution.cache[(s,p)] = s==""
            return s==""
        if p == s:
            Solution.cache[(s,p)]=True
            return True
        if s == "":
            if p == "":
                Solution.cache[(s,p)]=True
                return True
        ############### 边界检查部分End ###############
        if (s,p) in Solution.cache:
            return Solution.cache[(s,p)]
        ############### 小规模的问题Start ###############
        if len(s)>=1 and len(p)>=1 and self.isMatch(s[:-1], p[:-1]):
            if len(p) >= 1:
                if s[-1] == p[-1] or p[-1] == ".":
                    Solution.cache[(s,p)]=True
                    return True
        if len(s)>=1 and self.isMatch(s[:-1], p):
            if len(p) > 1:
                if (s[-1] == p[-2] or p[-2] == '.') and p[-1]=="*":
                    Solution.cache[(s,p)]=True
                    return True
        ############### 小规模的问题End ###############
        Solution.cache[(s,p)]=False
        return False

编程之禅：Debug

当我满心欢喜的开始调试的时候，发现 "aa"和"a*"就匹配不过去，debug思路如下

s="aa"; p="a*"

1. (s[:-1], p)? ? ? ==>? ? ?s="a"; p="a*"? ? ? ? ? ?应该是可以的
2. (s[:-1], p)? ? ? ==>? ? ?s=""; p="a*"? ? ? ? ? ? ?应该是可以的

然而【a*可以匹配空】这一条规则，在我的代码中并没有体现，于是我一开始把它放到了开头，就像这样

class Solution:
    cache = {}
    def isMatch(self, s: str, p: str) -> bool:
        if p == "":
            Solution.cache[(s,p)] = s==""
            return s==""
        if p == s:
            Solution.cache[(s,p)]=True
            return True
        if s == "":
            if p == "" or (len(p)==2 and p[-1]=="*"):   # 加在这里 表达【a*可以匹配空】这件事
                Solution.cache[(s,p)]=True
                return True

但是还没有提交，我就找了一个测试用例，s="b";?p="ba*"，果然没有通过，原因在于，如果把【a*可以匹配空】这件事用边界条件来表达，这就说明，需要一步一步去掉最后的字符【坍缩】到这个状态才能生效，而如果无法【坍缩】到最后这一步，比如p="ba*"，无论怎么从后面删减，也无法得到"a*"（总会有一个b），所以，应该再加一个转移方程。最终的代码就像这样：

class Solution:
    cache = {}
    def isMatch(self, s: str, p: str) -> bool:
        ############### 边界检查部分Start ###############
        if p == "":
            Solution.cache[(s,p)] = s==""
            return s==""
        if p == s:
            Solution.cache[(s,p)]=True
            return True
        if s == "":
            if p == "":
                Solution.cache[(s,p)]=True
                return True
        ############### 边界检查部分End ###############
        if (s,p) in Solution.cache:
            return Solution.cache[(s,p)]
        ############### 小规模的问题Start ###############
        if len(s)>=1 and len(p)>=1 and self.isMatch(s[:-1], p[:-1]):
            if len(p) >= 1:
                if s[-1] == p[-1] or p[-1] == ".":
                    Solution.cache[(s,p)]=True
                    return True
        if len(s)>=1 and self.isMatch(s[:-1], p):
            if len(p) > 1:
                if (s[-1] == p[-2] or p[-2] == '.') and p[-1]=="*":
                    Solution.cache[(s,p)]=True
                    return True
        if len(p)>=2 and self.isMatch(s, p[:-2]):
            if p[-1] == "*":                      # 表达【a*可以匹配空】这件事
                Solution.cache[(s,p)]=True
                return True
        ############### 小规模的问题End ###############
        Solution.cache[(s,p)]=False
        return False

总结

关于题目的部分就到这里了，现在解决文章中埋下的坑，以及我对这道题目的思考

1. 如何寻找小规模的问题

这里我给出两个思路，第一个比较好想，一般就是-1，-2这种，在只有一个变量的时候，比较简单，基本有一个就行。但在有两种变量的情况下，转移方程一定至少有两个，需要保证在所有情况下都能让情况【坍缩】到【边界条件】，在思考每种情况下成立的条件时，需要【尽可能的考虑题目中给出的条件】。另一个思路就是反过来想问题，将题目中给出能成立的可能拆解成条件。比如这道题，如果最后再审视完成的代码，可以清楚的看到，我们拆解出来的这三个【小规模问题】分别代表了题目中 . 和 * 的三种功能：

• 小规模问题1表示："."? ? 能代表任意字符
• 小规模问题2表示："*"? ?有延长匹配功能
• 小规模问题3表示："*"? ?也可以匹配空

总结建议：拿到题目进行分析后，尽量用思路2，梳理题目中成立的条件来整理转移方程，在尝试的时候可以用思路1，试着让规模-1，-2，然后利用题干中的条件让情况成立。

2. 在某一种情况下是否需要将所有条件写全

细心的读者可能发现了，这个代码中很多地方似乎并没有写全，比如在边界条件中，【*可以代表空】这个事情并没有写到边界条件中，再比如第二种情况，s和p都要加一个字符的时候，如果p的最后一个字符是*，是否也有可能成立呢？

其实是的，多测试几次你就会发现，上述几种情况写不写都无关紧要，重要的是我们已经把【题目中表达的几种成立的可能性通过小规模问题表达出来了】这件事，至于是在哪里表达的，似乎并不重要，这也是【递归】神奇的地方吧，只要我写了，总会掉到那里去

课后作业

给看到这里的同学一个大大的赞，最后留下一个小思考题，按照【总结】所说，尽量的按照题目中成立的可能设置【小规模问题】，那".*"可以匹配任意字符，这种特殊组合为什么没有成为小规模问题中的一个，或是出现在边界条件中呢？