正则表达式背后的秘密——详解 LeetCode 第十题

今天的任务首先要回顾下昨天刷的 LeetCode 第十题，同时，也想做一番尝试：把刷题笔记写的更丰富、可读性更强些，同时也整理些算法上的总结，以此锻炼下自己整理、输出能力。

相信学习过一段时间 Python 或其它编程语言的朋友都会或多或少接触“正则表达式”这个概念：

正则表达式，又称规则表达式。（英语：Regular Expression，在代码中常简写为regex、regexp或RE），计算机科学的一个概念。正则表达式通常被用来检索、替换那些符合某个模式(规则)的文本。 百度百科-正则表达式

比如我们有这么一段话：“今天是2020年4月19日星期天，勤劳的 TED 在整理 LeetCode 第十题。” 我们就可以制定提取数字的规则，然后应用到刚语句中提取出 2020、4、19 这些数字数据；或者我们制定提取英文字母的规则，提取 TED 这个英文名字。在 Python 中呢，我们就可以通过导入 re 模块来实现制定规则提取目标字符串的功能。

那么这套规则中呢，有两个特殊字符 '.' 和 '*'：

• '.' 匹配任意单个字符
• '*' 匹配零个或多个表达式

比如我现在制定刚提到的获取数字和字母的规则 p：

p = r"今天是(\d*)年(\d*)月(\d*)日星期天，勤劳的 (.*) 在整理 LeetCode 第十题。"

其中 \d 代表数字，\d* 就代表匹配 0 个数字或者多个数字；. 代表任意字符，.* 则表示零或多个任意字符（也就是随意什么都可以了）

试下这个规则能否拿到我们想要的：

简单正则表达式演示 这是简单的正则表达式应用的一个演示，也展现了两个特殊字符的功能。今天我们要回顾的 LeetCode 第十题呢就和这两个字符相关，要我们自己来设计实现 . 和 * 在正则表达式中实现的匹配功能。

题目

第 10 题 正则表达式匹配：

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

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

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

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例：

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching

思路

先回顾下昨天的思路，对于目标字符串 s 和规则字符串 p，我们根据 p 中的规则判断是否匹配 s 。又因为我们是来设计完成 "." 和 "*" 的功能，所以基本都会是围绕着二者展开。

首先看 ".", 如果只存在 "." 而不存在 "*", 那么 s 和 p 长度是相同的，只要逐位来检测 p 中的字符是否与 s 匹配：要么该位字符与 s 中相同，要么该位字符是 ".", 否则就会匹配失败。

对于这个 "." 的检测逻辑，大致代码内容如下：

p = "a.a"
s = "aaa"

for i,c in enumerate(p):
    if c not in [".", s[i]]:
        print(False)

接下来看 "*"，当出现该星号字符时，因为它是前一个字符的次数标志，那么它如果出现在首位 p[0] 是没有意义的。

那么如果它出现在第二位 p[1] 时：

• 星号如果是发挥零个前面字符的作用，那么 p[0]p[1] 这两个字符完全不参与对 s 的匹配，即 p[2:] 对 s 的匹配效果与 p 对 s 的匹配效果一致。换句话说，此时就可以将 p 的前两位删去来重新匹配检测
• 星号如果是发挥复制前面字符的作用，这时，我们可以对 s 字符串做文章，我们把 s 的首字符拿走，因为 * 可以将 p 中的字符转为个数 0 从而不影响匹配效果，即 p 对 s[1:] 的匹配效果和 p 对 s 的匹配效果是一致的。换言之此时可以将 s 的第一位删去来重新匹配检测

还有如果它没有出现在第二位 p[1] 呢？那对于前两位的检测需要按没有 * 时的匹配规则来检测，同时再把 p 和 s 检测通过的第一位同时删去，重新检测 p[1:] 和 s[1:] 是否匹配即可。

经过在第十题题解、评论区的洗礼，我们可以了解到以上思路的算法被称为回溯算法：

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 百度百科-回溯算法

结合着刚我们的分析，当我们发现 p 中出现 * 时，如果其在第二位出现，我们可以将 p 的前两位删去重新执行整个检测、或将 s 的首位删去重新执行整个检测；如果没在第二位出现，将 s 和 p 的第一位同时删去来进行重新匹配检测。这个满足重新匹配检测的状态点即“回溯点”。

代码实现

基于上述思路，我们先完成一版代码：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # 如果有 *      
        if "*" in p:            
            temp =  bool(s) and p[0] in [".",s[0]]
            if len(p)>1 and p[1]=="*":                           
                return self.isMatch(s,p[2:]) or (temp and self.isMatch(s[1:],p))
            else:
                return temp and self.isMatch(s[1:],p[1:])
        # 没 * 时如果 p 为空字符串
        elif p=="":
            if s=="":
                return True
            else:
                return False
        # 如果 p 为非空没 * 字符串
        else:
            if len(p)!=len(s):
                return False
            try:
                print("here")
                for i,c in enumerate(p):
                    if c not in [".", s[i]]:
                        print(c,s[i])
                        return False
                return True
            except:
                return False 

测试结果

中文区结果：

执行用时 :1384 ms, 在所有 Python3 提交中击败了32.14%的用户 内存消耗 :13.7 MB, 在所有 Python3 提交中击败了6.82%的用户

英文版结果：

Runtime: 1380 ms, faster than 14.81% of Python3 online submissions for Regular Expression Matching. Memory Usage: 14 MB, less than 5.55% of Python3 online submissions for Regular Expression Matching.

优化

参考其它回溯算法的代码，可能会比我上面写的简洁，比如把 p 为非空字符串的情况合并，无论是否有 * 号，都可以在其第二位不是星号时对 p 和 s 删去第一位来进行回溯，比如 LeetCode 发布的官方解：

class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern:
            return not text

        first_match = bool(text) and pattern[0] in {text[0], '.'}

        if len(pattern) >= 2 and pattern[1] == '*':
            return (self.isMatch(text, pattern[2:]) or
                    first_match and self.isMatch(text[1:], pattern))
        else:
            return first_match and self.isMatch(text[1:], pattern[1:])

#作者：LeetCode
#链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode/

但这种设计我觉得会将不含星号的情况给复杂化，所以我保留了自己对于是否含星号的判断处理。

除了回溯法，官方题解中还提到了动态规划方法，我也是初次接触这类思想或方法，查了下相关介绍：

动态规划的核心思想是把原问题分解成子问题进行求解，也就是分治的思想。 动态规划问题，大致可以通过以下四部进行解决。 1.划分状态，即划分子问题 2.状态表示，即如何让计算机理解子问题。 3.状态转移，即父问题是如何由子问题推导出来的。 4.确定边界，确定初始状态是什么？最小的子问题？最终状态又是什么。 我们实现动态规划算法，常用的是2个实现套路，一个是自底向上，另外一个是自顶向下。无论是何种方式，我们都要明确动态规划的过程，把状态表示、状态转移、边界都考虑好。 来源：https://baijiahao.baidu.com/s?id=1631319141857419948&wfr=spider&for=pc

其想法是通过 dp(i,j) 来表示 text[i:] 是否与 pattern[j:] 匹配，在自顶向下的动态规划算法中，同样采用了刚我们用过的回溯方法：

class Solution(object):
    def isMatch(self, text, pattern):
        # memo 字典用来存储(i,j)作为key，匹配结果作为值
        memo = {}
        # 定义储存(i,j)对应匹配结果到 memo字典的函数，同时还会返回该(i,j)对应的匹配结果
        def dp(i, j):
            # 如果字典中没有该key，即还没有对(i,j)进行检测
            if (i, j) not in memo:
                # 如果j超出pattern长度
                if j == len(pattern):
                    # 此时i必须也超出长度，否则返回False
                    ans = i == len(text)
                # 如果还在pattern中
                else:
                    # i也在text中且pattern在j处字符与text在i处字符相匹配
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    # 如果第二位是星号，dp(i,j)与dp(i,j+2)或在前面字符相符的情况下 dp(i+1,j)的结果等效
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    # 如果星号不在第二位，那么dp(i,j)与在之前字符相符情况下dp(i+1,j+1)等效
                    else:
                        ans = first_match and dp(i+1, j+1)
                # 因为这是字典中没有(i,j)作为key记录的情况，将其记录在字典中
                memo[i, j] = ans
            # 最终返回(i,j)作为key值在字典中对应的匹配结果值
            return memo[i, j]
        # 自顶向下，也就是从最终状态出发，如果遇到一个子问题还未求解，那么就先求解子问题。如果子问题已经求解，那么直接使用子问题的解
        return dp(0, 0)

#作者：LeetCode
#链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode/

结合着其代码和回溯算法流程，我试着加了如上注释。初次接触这些，让我看现在能看明白，但让我写就写不出来了。先接触和熟悉着，以后应该还会有题目练习这种动态规划的，到时在继续巩固理解和加深印象。

神奇的是动态规划的测试结果：

Runtime: 32 ms, faster than 98.37% of Python3 online submissions for Regular Expression Matching. Memory Usage: 14.2 MB, less than 5.55% of Python3 online submissions for Regular Expression Matching. 执行用时 :44 ms, 在所有 Python3 提交中击败了96.37%的用户 内存消耗 :13.9 MB, 在所有 Python3 提交中击败了6.82%的用户

对于此，官方代码给的时间复杂度分析如下：

时间复杂度：用 T 和 P 分别表示匹配串和模式串的长度。对于i=0, … , Ti=0,…,T 和 j=0, … , Pj=0,…,P 每一个 dp(i, j)只会被计算一次，所以后面每次调用都是 O(1)O(1) 的时间。因此，总时间复杂度为 O(TP) 。

结论

对于回溯算法，我的理解是当我们第一次调用函数时，将其等效成为对新的参数再执行一遍函数的问题，而新一轮的参数是与之前相关联的，由此即可通过函数内再继续调用函数一直找到根源处的结果再来整合成最终结果。

动态规划呢，就是将我们刚才找到的新旧参数之间的关系、以及函数内调用函数的条件和状态等都定义好，然后直接启动就行了。在整个过程中，其设计是可以明显降低时间复杂度的。（仅从结果分析，原因等之后理解深了再来回答吧）

初次接触，可能理解比较笼统，不对的地方还请大家指正～