--- title: '动态规划之正则表达' tags: ['动态规划', '字符串'] ---
![](https://labuladong.github.io/pictures/souyisou1.png) **通知:[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.1,[手把手刷二叉树系列课程](https://aep.xet.tech/s/3YGcq3) 上线。[第 18 期每日打卡](https://aep.xet.tech/s/2PLO1n) 开始报名。反馈或修正 chatGPT 翻译的多语言代码 [点击这里](https://github.com/labuladong/fucking-algorithm/issues/1113)。另外,建议你在我的 [网站](https://labuladong.github.io/algo/) 学习文章,体验更好。** 读完本文,你不仅学会了算法套路,还可以顺便解决如下题目: | LeetCode | 力扣 | 难度 | | :----: | :----: | :----: | | [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/) | [10. 正则表达式匹配](https://leetcode.cn/problems/regular-expression-matching/) | 🔴 | - | [剑指 Offer 19. 正则表达式匹配](https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/) | 🔴 **-----------** 正则表达式是一个非常强力的工具,本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「正则表达式匹配」就要求我们实现一个简单的正则匹配算法,包括「.」通配符和「*」通配符。 这两个通配符是最常用的,其中点号「.」可以匹配任意一个字符,星号「*」可以让之前的那个字符重复任意次数(包括 0 次)。 比如说模式串 `".a*b"` 就可以匹配文本 `"zaaab"`,也可以匹配 `"cb"`;模式串 `"a..b"` 可以匹配文本 `"amnb"`;而模式串 `".*"` 就比较牛逼了,它可以匹配任何文本。 题目会给我们输入两个字符串 `s` 和 `p`,`s` 代表文本,`p` 代表模式串,请你判断模式串 `p` 是否可以匹配文本 `s`。我们可以假设模式串只包含小写字母和上述两种通配符且一定合法,不会出现 `*a` 或者 `b**` 这种不合法的模式串, 函数签名如下: ```cpp bool isMatch(string s, string p); ``` 对于我们将要实现的这个正则表达式,难点在那里呢? 点号通配符其实很好实现,`s` 中的任何字符,只要遇到 `.` 通配符,无脑匹配就完事了。主要是这个星号通配符不好实现,一旦遇到 `*` 通配符,前面的那个字符可以选择重复一次,可以重复多次,也可以一次都不出现,这该怎么办? 对于这个问题,答案很简单,对于所有可能出现的情况,全部穷举一遍,只要有一种情况可以完成匹配,就认为 `p` 可以匹配 `s`。那么一旦涉及两个字符串的穷举,我们就应该条件反射地想到动态规划的技巧了。 ### 一、思路分析 我们先脑补一下,`s` 和 `p` 相互匹配的过程大致是,两个指针 `i, j` 分别在 `s` 和 `p` 上移动,如果最后两个指针都能移动到字符串的末尾,那么久匹配成功,反之则匹配失败。 **如果不考虑 `*` 通配符,面对两个待匹配字符 `s[i]` 和 `p[j]`,我们唯一能做的就是看他俩是否匹配**: ```cpp bool isMatch(string s, string p) { int i = 0, j = 0; while (i < s.size() && j < p.size()) { // 「.」通配符就是万金油 if (s[i] == p[j] || p[j] == '.') { // 匹配,接着匹配 s[i+1..] 和 p[j+1..] i++; j++; } else { // 不匹配 return false; } } return i == j; } ``` 那么考虑一下,如果加入 `*` 通配符,局面就会稍微复杂一些,不过只要分情况来分析,也不难理解。 **当 `p[j + 1]` 为 `*` 通配符时,我们分情况讨论下**: 1、如果 `s[i] == p[j]`,那么有两种情况: 1.1 `p[j]` 有可能会匹配多个字符,比如 `s = "aaa", p = "a*"`,那么 `p[0]` 会通过 `*` 匹配 3 个字符 `"a"`。 1.2 `p[i]` 也有可能匹配 0 个字符,比如 `s = "aa", p = "a*aa"`,由于后面的字符可以匹配 `s`,所以 `p[0]` 只能匹配 0 次。 2、如果 `s[i] != p[j]`,只有一种情况: `p[j]` 只能匹配 0 次,然后看下一个字符是否能和 `s[i]` 匹配。比如说 `s = "aa", p = "b*aa"`,此时 `p[0]` 只能匹配 0 次。 综上,可以把之前的代码针对 `*` 通配符进行一下改造: ```cpp if (s[i] == p[j] || p[j] == '.') { // 匹配 if (j < p.size() - 1 && p[j + 1] == '*') { // 有 * 通配符,可以匹配 0 次或多次 } else { // 无 * 通配符,老老实实匹配 1 次 i++; j++; } } else { // 不匹配 if (j < p.size() - 1 && p[j + 1] == '*') { // 有 * 通配符,只能匹配 0 次 } else { // 无 * 通配符,匹配无法进行下去了 return false; } } ``` 整体的思路已经很清晰了,但现在的问题是,遇到 `*` 通配符时,到底应该匹配 0 次还是匹配多次?多次是几次? 你看,这就是一个做「选择」的问题,要把所有可能的选择都穷举一遍才能得出结果。动态规划算法的核心就是「状态」和「选择」,**「状态」无非就是 `i` 和 `j` 两个指针的位置,「选择」就是 `p[j]` 选择匹配几个字符**。 ### 二、动态规划解法 根据「状态」,我们可以定义一个 `dp` 函数: ```cpp bool dp(string& s, int i, string& p, int j); ```