010.正则式匹配
作者：沉默王二 发布时间：2024-01-17T21:25:50.524+0800
技术派阅读地址：https://paicoding.com/column/7/10
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出三道大家完全都能掌握的题解，大家会非常容易掌握。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，我不知道什么是算法，但是我知道二哥写的 LeetCode 题解真不错。
题意
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个字符
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例
输入：s = "aa", p = "a"
解释："a" 无法匹配 "aa" 整个字符串。
输入：s = "aa", p = "a*"
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 前面的字符是 'a'，因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入：s = "ab", p = ".*"
解释："." 表示可匹配零个或多个（''）任意字符（'.'）。
提示
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s 只包含从 a-z 的小写字母。
- p 只包含从 a-z 的小写字母，以及字符 . 和 *。
- 保证每次出现字符 * 时，前面都匹配到有效的字符
难度
难
分析 1
正则表达式其实是一个非常宏大的知识体系，在日常开发中其实也蛮常用，尤其是做一些数据校验的时候，比如说手机号码、邮箱、身份证号码等等，都可以通过正则表达式来进行校验。
还有一些处理复杂字符串的时候，比如说我要通过一定的规则从一个庞大的字符序列中找出想要的内容，比如说从 HTML 页面的源码中找出标题、作者、正文等，那由于 HTML 页面的结构比较复杂，我们就需要通过正则表达式来进行匹配查找。
如果之前没有了解过正则表达式的话，可以先通过 B站上这个视频进行了解：
https://www.bilibili.com/video/BV1da4y1p7iZ
如果觉得 10 分钟的视频还是太长，想要文档，那么推荐大家看看 GitHub 上这个仓库：
https://github.com/cdoco/learn-regex-zh
大致了解正则表达式是什么，有什么作用后，对这道题会有更清晰的解题思路。
一句话总结下：正则表达式就是一种用来匹配字符串的规则。
上面是一个比较简单的正则表达式，具体解释如下：
- ^：匹配输入字符串的开始位置。
- [a-zA-Z0-9_-]：字符集合。匹配所有小写字母 (a-z)、大写字母 (A-Z)、数字 (0-9)，以及下划线 (_) 和中划线 (-)。
- {3,15}：表示匹配 3-15 个前面的字符。
- $：匹配输入字符串的结束位置。
所以这个正则表达式的意思就是：匹配一个长度为 3-15 个字符的字符串，且只能包含小写字母、大写字母、数字、下划线和中划线。
回到本题，s 只包含从 a-z 的小写字母；p 只包含从 a-z 的小写字母，以及字符 . 和 *。
如果只有.的话，事情就很简单，因为 . 可以匹配任意单个字符，所以我们只需要遍历 s 和 p，然后逐个字符进行匹配即可。
但是这里还有一个*，*就比较麻烦了，因为它可以匹配零个或多个前面的那一个字符。
所以我们需要考虑的情况就变得多了，比如说：
- s = "aa", p = "a*"：这种情况下，可以匹配零个或多个前面的那一个字符，所以a可以匹配""、"a"、"aa"，所以这种情况下是可以匹配的。
- s = "ab", p = ".*"：这种情况下，.*可以匹配零个或多个前面的任意字符，所以.*可以匹配""、"a"、"ab"、"abb"、"abbb"、"abbbb"，所以这种情况下是可以匹配的。
所以我们需要*的前一个字符到底能够匹配多少个字符。我打算先采用递归的方式来处理，这样的思路会比较简单、直接、暴力。
递归方法的核心在于将问题分解成更小的子问题。对于每一个字符，我们需要判断它是否与模式中的字符匹配，然后递归地处理剩余的字符串。
①、基本情况：如果模式字符串 pattern 为空，那么输入字符串 text 也必须为空才能匹配成功。
②、匹配第一个字符：检查text和pattern的第一个字符是否相等，或者模式字符为'.'，因为'.'可以匹配任何单个字符。
③、处理*字符：当模式的第二个字符是*时，我们需要考虑两种情况：
- pattern.substring(2)：跳过这一部分的模式，因为可以表示它前面的字符出现0次（x）。
- text.substring(1)与pattern：如果当前字符匹配，则检查text的下一个字符，因为 * 可以表示多次。
④、其他情况：如果模式的第二个字符不是*，则需要当前字符匹配，并且剩余的字符串和模式也需要匹配。
来看代码：
class Solution {
// 基本情况：如果模式串为空，那么输入字符串也必须为空才匹配 if (pattern.isEmpty()) return text.isEmpty();
// 检查第一个字符是否匹配（考虑'.'的情况） boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
// 如果模式的下一个字符是'*' if (pattern.length() >= 2 && pattern.charAt(1) == '*'){ // 两种情况： // 1. 忽略模式中的这两个字符（'x*'），因为'*'可以表示前面的字符出现0次 // 2. 删除匹配的字符串中的一个字符（如果它能与模式中的'x'匹配），因为'*'可以表示多次 return (isMatch(text, pattern.substring(2)) || (first_match && isMatch(text.substring(1), pattern))); } else { // 如果下一个字符不是'*'，则直接比较当前字符，并递归处理剩余部分 return first_match && isMatch(text.substring(1), pattern.substring(1)); } }}
很容易懂，但很可惜效率不高，只能击败 5% 的用户。
分析 2
递归的效率很低，但是思路很清晰，那么我们能不能通过其他的方式来提高效率呢？
可以使用记忆法，也就是将已经计算过的结果存储起来，以避免重复计算，对于这道题，我们可以使用一个二维数组来作为缓存，来存储已经计算过的结果。
这样在递归调用中，如果遇到相同的子问题，我们可以直接从缓存中返回结果，而不是重新计算。
来看题解。
class Solution {
Boolean[][] memo;
public boolean isMatch(String text, String pattern) { // 初始化记忆矩阵，未计算的值为null memo = new Boolean[text.length() + 1][pattern.length() + 1]; // 从字符串和模式的开头开始递归匹配 return dp(0, 0, text, pattern); }
public boolean dp(int i, int j, String text, String pattern) { // 如果这个子问题已经计算过，则直接返回结果 if (memo[i][j] != null) { return memo[i][j]; } boolean ans; // 如果模式已经走到了末尾，返回text是否也走到了末尾 if (j == pattern.length()) { ans = i == text.length(); } else { // 检查text当前字符和pattern当前字符是否匹配 boolean first_match = (i < text.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
// 如果模式中下一个字符是'*' if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') { // '*'匹配0次的情况 || '*'匹配1次或多次的情况 ans = (dp(i, j + 2, text, pattern) || first_match && dp(i + 1, j, text, pattern)); } else { // 如果下一个字符不是'*'，则继续递归检查下一个字符 ans = first_match && dp(i + 1, j + 1, text, pattern); } } // 计算完毕，存储结果 memo[i][j] = ans; return ans; }}
详细解释：
①、我们定义一个 memo 二维数组作为缓存。memo[i][j] 表示 text 从索引 i 开始的子串和 pattern 从索引 j 开始的子模式是否匹配。
②、isMatch 方法是解决问题的入口。
③、dp 方法是递归的核心，它接受 text 和 pattern 的索引 i 和 j。
④、在 dp 方法开始时，我们首先检查是否已经计算过当前的子问题。如果 memo[i][j] 不是 null，我们直接返回它的值。
⑤、如果模式 pattern 已经检查完毕 (j == pattern.length ())，则 text 也应该同时检查完毕 (i == text.length ())，这样才算匹配成功。
⑥、如果模式未检查完毕，我们首先确定 text 当前字符是否与 pattern 当前字符匹配。这里有两种情况：字符直接相等，或者 pattern 的字符是 .。
⑦、接下来，如果 pattern 中下一个字符是 *，我们有两个选择：
- 忽略 pattern 中的这两个字符（即 * 前面的字符和 *），因为 * 可以表示前面的字符出现0次。
- 如果 text 当前字符与 pattern 的 * 前面的字符匹配，我们可以继续递归地检查 text 的下一个字符，而 pattern 不变，因为 * 可以表示多次。
⑧、如果下一个字符不是 *，我们简单地递归调用下一个字符。
⑨、在递归结束时，我们将结果存储在 memo 中，并返回结果。
归通过存储子问题的结果来避免重复计算，这样，即使我们使用递归的方法，也能提高算法的效率。这种方法通常会将时间复杂度降低到接近动态规划的级别。
果不其然，效率飙升，击败 100% 的用户。
分析 3
**第 5 题 **的时候，我们就讲过动态规划了，那这道题其实用动态规划来做就非常合适。
我们先来看看动态规划的思路，然后再来看看怎么转移方程。
当然，让我按照您提出的结构来详细解释第二个题解的解题步骤。
1. 状态定义
我们定义一个二维布尔数组 dp，其中 dp[i][j] 表示字符串 text 的前 i 个字符与模式串 pattern 的前 j 个字符是否能够匹配。这里，i 和 j 分别代表 text 和 pattern 的子串长度。
2. 状态转移方程
状态转移是根据 pattern 的当前字符和它之前的字符来更新 dp 数组。以下是转移方程的详细说明：
①、当 pattern[j - 1] 是普通字符或 . 时，如果 pattern[j - 1] 等于 text[i - 1] 或者 pattern[j - 1] 是 .，则 dp[i][j] = dp[i - 1][j - 1]。这是因为当前字符匹配，所以匹配结果取决于剩余的子串。
②、当 pattern[j - 1] 是 '*' 时，有两种情况：
- 如果 '' 前的字符不匹配 text[i - 1]，即 pattern[j - 2] != text[i - 1] 且 pattern[j - 2] 不是 .，则 dp[i][j] = dp[i][j - 2]。这表示 '' 使得其前一个字符在 text 中出现 0 次。
- 如果 '' 前的字符匹配 text[i - 1] 或 pattern[j - 2] 是 .，则 dp[i][j] = dp[i][j - 2] || dp[i - 1][j]。这表示 '' 可以使得其前一个字符在 text 中出现 0 次或多次。
3. 初始状态
初始状态是动态规划的起点。我们需要正确地初始化 dp 数组：
- dp[0][0] = true; 表示两个空字符串能够匹配。
- 对于 pattern 中的每个字符，如果当前字符是 '*'，则需要检查它是否能使得 pattern 的这一部分与空字符串 text 匹配。如果是的话，则 dp[0][j] = dp[0][j - 2]。
4. 返回值
最终，dp[text.length ()][pattern.length ()] 的值表示整个字符串 text 是否与模式串 pattern 匹配。
来看代码：
class Solution {
// 状态定义：dp[i][j] 表示 text 的前 i 个字符和 pattern 的前 j 个字符是否匹配 boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1]; // 初始状态：空字符串是可以匹配的 dp[0][0] = true; for (int j = 2; j <= pattern.length(); j++) { if (pattern.charAt(j - 1) == '') { dp[0][j] = dp[0][j - 2]; } } // 状态转移方程 for (int i = 1; i <= text.length(); i++) { for (int j = 1; j <= pattern.length() ; j++) { if (pattern.charAt(j - 1) == '') { // 如果 pattern 的第 j 个字符是 ''，则需要考虑 pattern 的第 j - 1 个字符 pattern[j - 1] if (pattern.charAt(j - 2) == text.charAt(i - 1) || pattern.charAt(j - 2) == '.') { // 如果 pattern[j - 1] 为小写字母，那么 pattern[j - 1] 可以出现 0 次或多次 // 如果 pattern[j - 1] 为 '.'，那么 pattern[j - 1] 可以出现 0 次或多次 dp[i][j] = dp[i][j - 2] || dp[i - 1][j]; } else { // 如果 pattern[j - 1] 为 ''，那么 pattern[j - 1] 可以出现 0 次或多次 dp[i][j] = dp[i][j - 2]; } } else { // 如果 pattern 的第 j 个字符不是 '*'，则需要考虑 pattern 的第 j 个字符 pattern[j - 1] if (pattern.charAt(j - 1) == text.charAt(i - 1) || pattern.charAt(j - 1) == '.') { // 如果 pattern[j - 1] 为小写字母，那么 text[i - 1] 和 pattern[j - 1] 必须匹配 // 如果 pattern[j - 1] 为 '.'，那么 text[i - 1] 和 pattern[j - 1] 必须匹配 dp[i][j] = dp[i - 1][j - 1]; } } } } // 返回值 return dp[text.length()][pattern.length()]; }}
效率也不错。
总结
这道题的难度是困难，但是我们通过递归、记忆法、动态规划三种方式来循序渐进地解决，相信大家都能掌握了。
第一种方法最直观，基本上用到的知识也是 Java 基础当中必须要掌握的，比如说字符串的截取、字符串的比较等等。
推荐大家认真读一下二哥的 Java 进阶之路中字符串和数组相关的内容：
另外，关于动态规划，我也找了一个帖子供大家参考和学习：
视频的话，我也帮大家找了一个，讲的还不错。
力扣链接：https://leetcode.cn/problems/regular-expression-matching/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4200+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
技术派阅读地址：https://paicoding.com/column/7/10
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出三道大家完全都能掌握的题解，大家会非常容易掌握。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，我不知道什么是算法，但是我知道二哥写的 LeetCode 题解真不错。
题意
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个字符
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例
输入：s = "aa", p = "a"
解释："a" 无法匹配 "aa" 整个字符串。
输入：s = "aa", p = "a*"
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 前面的字符是 'a'，因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入：s = "ab", p = ".*"
解释："." 表示可匹配零个或多个（''）任意字符（'.'）。
提示
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s 只包含从 a-z 的小写字母。
- p 只包含从 a-z 的小写字母，以及字符 . 和 *。
- 保证每次出现字符 * 时，前面都匹配到有效的字符
难度
难
分析 1
正则表达式其实是一个非常宏大的知识体系，在日常开发中其实也蛮常用，尤其是做一些数据校验的时候，比如说手机号码、邮箱、身份证号码等等，都可以通过正则表达式来进行校验。
还有一些处理复杂字符串的时候，比如说我要通过一定的规则从一个庞大的字符序列中找出想要的内容，比如说从 HTML 页面的源码中找出标题、作者、正文等，那由于 HTML 页面的结构比较复杂，我们就需要通过正则表达式来进行匹配查找。
如果之前没有了解过正则表达式的话，可以先通过 B站上这个视频进行了解：
https://www.bilibili.com/video/BV1da4y1p7iZ
如果觉得 10 分钟的视频还是太长，想要文档，那么推荐大家看看 GitHub 上这个仓库：
https://github.com/cdoco/learn-regex-zh
大致了解正则表达式是什么，有什么作用后，对这道题会有更清晰的解题思路。
一句话总结下：正则表达式就是一种用来匹配字符串的规则。
上面是一个比较简单的正则表达式，具体解释如下：
- ^：匹配输入字符串的开始位置。
- [a-zA-Z0-9_-]：字符集合。匹配所有小写字母 (a-z)、大写字母 (A-Z)、数字 (0-9)，以及下划线 (_) 和中划线 (-)。
- {3,15}：表示匹配 3-15 个前面的字符。
- $：匹配输入字符串的结束位置。
所以这个正则表达式的意思就是：匹配一个长度为 3-15 个字符的字符串，且只能包含小写字母、大写字母、数字、下划线和中划线。
回到本题，s 只包含从 a-z 的小写字母；p 只包含从 a-z 的小写字母，以及字符 . 和 *。
如果只有.的话，事情就很简单，因为 . 可以匹配任意单个字符，所以我们只需要遍历 s 和 p，然后逐个字符进行匹配即可。
但是这里还有一个*，*就比较麻烦了，因为它可以匹配零个或多个前面的那一个字符。
所以我们需要考虑的情况就变得多了，比如说：
- s = "aa", p = "a*"：这种情况下，可以匹配零个或多个前面的那一个字符，所以a可以匹配""、"a"、"aa"，所以这种情况下是可以匹配的。
- s = "ab", p = ".*"：这种情况下，.*可以匹配零个或多个前面的任意字符，所以.*可以匹配""、"a"、"ab"、"abb"、"abbb"、"abbbb"，所以这种情况下是可以匹配的。
所以我们需要*的前一个字符到底能够匹配多少个字符。我打算先采用递归的方式来处理，这样的思路会比较简单、直接、暴力。
递归方法的核心在于将问题分解成更小的子问题。对于每一个字符，我们需要判断它是否与模式中的字符匹配，然后递归地处理剩余的字符串。
①、基本情况：如果模式字符串 pattern 为空，那么输入字符串 text 也必须为空才能匹配成功。
②、匹配第一个字符：检查text和pattern的第一个字符是否相等，或者模式字符为'.'，因为'.'可以匹配任何单个字符。
③、处理*字符：当模式的第二个字符是*时，我们需要考虑两种情况：
- pattern.substring(2)：跳过这一部分的模式，因为可以表示它前面的字符出现0次（x）。
- text.substring(1)与pattern：如果当前字符匹配，则检查text的下一个字符，因为 * 可以表示多次。
④、其他情况：如果模式的第二个字符不是*，则需要当前字符匹配，并且剩余的字符串和模式也需要匹配。
来看代码：
class Solution {
// 基本情况：如果模式串为空，那么输入字符串也必须为空才匹配 if (pattern.isEmpty()) return text.isEmpty();
// 检查第一个字符是否匹配（考虑'.'的情况） boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
// 如果模式的下一个字符是'*' if (pattern.length() >= 2 && pattern.charAt(1) == '*'){ // 两种情况： // 1. 忽略模式中的这两个字符（'x*'），因为'*'可以表示前面的字符出现0次 // 2. 删除匹配的字符串中的一个字符（如果它能与模式中的'x'匹配），因为'*'可以表示多次 return (isMatch(text, pattern.substring(2)) || (first_match && isMatch(text.substring(1), pattern))); } else { // 如果下一个字符不是'*'，则直接比较当前字符，并递归处理剩余部分 return first_match && isMatch(text.substring(1), pattern.substring(1)); } }}
很容易懂，但很可惜效率不高，只能击败 5% 的用户。
分析 2
递归的效率很低，但是思路很清晰，那么我们能不能通过其他的方式来提高效率呢？
可以使用记忆法，也就是将已经计算过的结果存储起来，以避免重复计算，对于这道题，我们可以使用一个二维数组来作为缓存，来存储已经计算过的结果。
这样在递归调用中，如果遇到相同的子问题，我们可以直接从缓存中返回结果，而不是重新计算。
来看题解。
class Solution {
Boolean[][] memo;
public boolean isMatch(String text, String pattern) { // 初始化记忆矩阵，未计算的值为null memo = new Boolean[text.length() + 1][pattern.length() + 1]; // 从字符串和模式的开头开始递归匹配 return dp(0, 0, text, pattern); }
public boolean dp(int i, int j, String text, String pattern) { // 如果这个子问题已经计算过，则直接返回结果 if (memo[i][j] != null) { return memo[i][j]; } boolean ans; // 如果模式已经走到了末尾，返回text是否也走到了末尾 if (j == pattern.length()) { ans = i == text.length(); } else { // 检查text当前字符和pattern当前字符是否匹配 boolean first_match = (i < text.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
// 如果模式中下一个字符是'*' if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') { // '*'匹配0次的情况 || '*'匹配1次或多次的情况 ans = (dp(i, j + 2, text, pattern) || first_match && dp(i + 1, j, text, pattern)); } else { // 如果下一个字符不是'*'，则继续递归检查下一个字符 ans = first_match && dp(i + 1, j + 1, text, pattern); } } // 计算完毕，存储结果 memo[i][j] = ans; return ans; }}
详细解释：
①、我们定义一个 memo 二维数组作为缓存。memo[i][j] 表示 text 从索引 i 开始的子串和 pattern 从索引 j 开始的子模式是否匹配。
②、isMatch 方法是解决问题的入口。
③、dp 方法是递归的核心，它接受 text 和 pattern 的索引 i 和 j。
④、在 dp 方法开始时，我们首先检查是否已经计算过当前的子问题。如果 memo[i][j] 不是 null，我们直接返回它的值。
⑤、如果模式 pattern 已经检查完毕 (j == pattern.length ())，则 text 也应该同时检查完毕 (i == text.length ())，这样才算匹配成功。
⑥、如果模式未检查完毕，我们首先确定 text 当前字符是否与 pattern 当前字符匹配。这里有两种情况：字符直接相等，或者 pattern 的字符是 .。
⑦、接下来，如果 pattern 中下一个字符是 *，我们有两个选择：
- 忽略 pattern 中的这两个字符（即 * 前面的字符和 *），因为 * 可以表示前面的字符出现0次。
- 如果 text 当前字符与 pattern 的 * 前面的字符匹配，我们可以继续递归地检查 text 的下一个字符，而 pattern 不变，因为 * 可以表示多次。
⑧、如果下一个字符不是 *，我们简单地递归调用下一个字符。
⑨、在递归结束时，我们将结果存储在 memo 中，并返回结果。
归通过存储子问题的结果来避免重复计算，这样，即使我们使用递归的方法，也能提高算法的效率。这种方法通常会将时间复杂度降低到接近动态规划的级别。
果不其然，效率飙升，击败 100% 的用户。
分析 3
**第 5 题 **的时候，我们就讲过动态规划了，那这道题其实用动态规划来做就非常合适。
我们先来看看动态规划的思路，然后再来看看怎么转移方程。
当然，让我按照您提出的结构来详细解释第二个题解的解题步骤。
1. 状态定义
我们定义一个二维布尔数组 dp，其中 dp[i][j] 表示字符串 text 的前 i 个字符与模式串 pattern 的前 j 个字符是否能够匹配。这里，i 和 j 分别代表 text 和 pattern 的子串长度。
2. 状态转移方程
状态转移是根据 pattern 的当前字符和它之前的字符来更新 dp 数组。以下是转移方程的详细说明：
①、当 pattern[j - 1] 是普通字符或 . 时，如果 pattern[j - 1] 等于 text[i - 1] 或者 pattern[j - 1] 是 .，则 dp[i][j] = dp[i - 1][j - 1]。这是因为当前字符匹配，所以匹配结果取决于剩余的子串。
②、当 pattern[j - 1] 是 '*' 时，有两种情况：
- 如果 '' 前的字符不匹配 text[i - 1]，即 pattern[j - 2] != text[i - 1] 且 pattern[j - 2] 不是 .，则 dp[i][j] = dp[i][j - 2]。这表示 '' 使得其前一个字符在 text 中出现 0 次。
- 如果 '' 前的字符匹配 text[i - 1] 或 pattern[j - 2] 是 .，则 dp[i][j] = dp[i][j - 2] || dp[i - 1][j]。这表示 '' 可以使得其前一个字符在 text 中出现 0 次或多次。
3. 初始状态
初始状态是动态规划的起点。我们需要正确地初始化 dp 数组：
- dp[0][0] = true; 表示两个空字符串能够匹配。
- 对于 pattern 中的每个字符，如果当前字符是 '*'，则需要检查它是否能使得 pattern 的这一部分与空字符串 text 匹配。如果是的话，则 dp[0][j] = dp[0][j - 2]。
4. 返回值
最终，dp[text.length ()][pattern.length ()] 的值表示整个字符串 text 是否与模式串 pattern 匹配。
来看代码：
class Solution {
// 状态定义：dp[i][j] 表示 text 的前 i 个字符和 pattern 的前 j 个字符是否匹配 boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1]; // 初始状态：空字符串是可以匹配的 dp[0][0] = true; for (int j = 2; j <= pattern.length(); j++) { if (pattern.charAt(j - 1) == '') { dp[0][j] = dp[0][j - 2]; } } // 状态转移方程 for (int i = 1; i <= text.length(); i++) { for (int j = 1; j <= pattern.length() ; j++) { if (pattern.charAt(j - 1) == '') { // 如果 pattern 的第 j 个字符是 ''，则需要考虑 pattern 的第 j - 1 个字符 pattern[j - 1] if (pattern.charAt(j - 2) == text.charAt(i - 1) || pattern.charAt(j - 2) == '.') { // 如果 pattern[j - 1] 为小写字母，那么 pattern[j - 1] 可以出现 0 次或多次 // 如果 pattern[j - 1] 为 '.'，那么 pattern[j - 1] 可以出现 0 次或多次 dp[i][j] = dp[i][j - 2] || dp[i - 1][j]; } else { // 如果 pattern[j - 1] 为 ''，那么 pattern[j - 1] 可以出现 0 次或多次 dp[i][j] = dp[i][j - 2]; } } else { // 如果 pattern 的第 j 个字符不是 '*'，则需要考虑 pattern 的第 j 个字符 pattern[j - 1] if (pattern.charAt(j - 1) == text.charAt(i - 1) || pattern.charAt(j - 1) == '.') { // 如果 pattern[j - 1] 为小写字母，那么 text[i - 1] 和 pattern[j - 1] 必须匹配 // 如果 pattern[j - 1] 为 '.'，那么 text[i - 1] 和 pattern[j - 1] 必须匹配 dp[i][j] = dp[i - 1][j - 1]; } } } } // 返回值 return dp[text.length()][pattern.length()]; }}
效率也不错。
总结
这道题的难度是困难，但是我们通过递归、记忆法、动态规划三种方式来循序渐进地解决，相信大家都能掌握了。
第一种方法最直观，基本上用到的知识也是 Java 基础当中必须要掌握的，比如说字符串的截取、字符串的比较等等。
推荐大家认真读一下二哥的 Java 进阶之路中字符串和数组相关的内容：
另外，关于动态规划，我也找了一个帖子供大家参考和学习：
视频的话，我也帮大家找了一个，讲的还不错。
力扣链接：https://leetcode.cn/problems/regular-expression-matching/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4200+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
技术派阅读地址：https://paicoding.com/column/7/10
-
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
-
这道题可以说完全重写了，给出三道大家完全都能掌握的题解，大家会非常容易掌握。
-
增加代码注释，这样大家更容易看懂并掌握题解；
-
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
-
增加手绘图，这样大家更容易理解解题思路；
-
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
-
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
-
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
-
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
鲁迅说过，我不知道什么是算法，但是我知道二哥写的 LeetCode 题解真不错。
题意
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- '.' 匹配任意单个字符
- '*' 匹配零个或多个前面的那一个字符
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例
输入：s = "aa", p = "a"
解释："a" 无法匹配 "aa" 整个字符串。
输入：s = "aa", p = "a*"
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 前面的字符是 'a'，因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入：s = "ab", p = ".*"
解释："." 表示可匹配零个或多个（''）任意字符（'.'）。
提示
- 1 <= s.length <= 20
- 1 <= p.length <= 20
- s 只包含从 a-z 的小写字母。
- p 只包含从 a-z 的小写字母，以及字符 . 和 *。
- 保证每次出现字符 * 时，前面都匹配到有效的字符
难度
难
分析 1
正则表达式其实是一个非常宏大的知识体系，在日常开发中其实也蛮常用，尤其是做一些数据校验的时候，比如说手机号码、邮箱、身份证号码等等，都可以通过正则表达式来进行校验。
还有一些处理复杂字符串的时候，比如说我要通过一定的规则从一个庞大的字符序列中找出想要的内容，比如说从 HTML 页面的源码中找出标题、作者、正文等，那由于 HTML 页面的结构比较复杂，我们就需要通过正则表达式来进行匹配查找。
如果之前没有了解过正则表达式的话，可以先通过 B站上这个视频进行了解：
https://www.bilibili.com/video/BV1da4y1p7iZ
如果觉得 10 分钟的视频还是太长，想要文档，那么推荐大家看看 GitHub 上这个仓库：
https://github.com/cdoco/learn-regex-zh
大致了解正则表达式是什么，有什么作用后，对这道题会有更清晰的解题思路。
一句话总结下：正则表达式就是一种用来匹配字符串的规则。
上面是一个比较简单的正则表达式，具体解释如下：
- ^：匹配输入字符串的开始位置。
- [a-zA-Z0-9_-]：字符集合。匹配所有小写字母 (a-z)、大写字母 (A-Z)、数字 (0-9)，以及下划线 (_) 和中划线 (-)。
- {3,15}：表示匹配 3-15 个前面的字符。
- $：匹配输入字符串的结束位置。
所以这个正则表达式的意思就是：匹配一个长度为 3-15 个字符的字符串，且只能包含小写字母、大写字母、数字、下划线和中划线。
回到本题，s 只包含从 a-z 的小写字母；p 只包含从 a-z 的小写字母，以及字符 . 和 *。
如果只有.的话，事情就很简单，因为 . 可以匹配任意单个字符，所以我们只需要遍历 s 和 p，然后逐个字符进行匹配即可。
但是这里还有一个*，*就比较麻烦了，因为它可以匹配零个或多个前面的那一个字符。
所以我们需要考虑的情况就变得多了，比如说：
- s = "aa", p = "a*"：这种情况下，可以匹配零个或多个前面的那一个字符，所以a可以匹配""、"a"、"aa"，所以这种情况下是可以匹配的。
- s = "ab", p = ".*"：这种情况下，.*可以匹配零个或多个前面的任意字符，所以.*可以匹配""、"a"、"ab"、"abb"、"abbb"、"abbbb"，所以这种情况下是可以匹配的。
所以我们需要*的前一个字符到底能够匹配多少个字符。我打算先采用递归的方式来处理，这样的思路会比较简单、直接、暴力。
递归方法的核心在于将问题分解成更小的子问题。对于每一个字符，我们需要判断它是否与模式中的字符匹配，然后递归地处理剩余的字符串。
①、基本情况：如果模式字符串 pattern 为空，那么输入字符串 text 也必须为空才能匹配成功。
②、匹配第一个字符：检查text和pattern的第一个字符是否相等，或者模式字符为'.'，因为'.'可以匹配任何单个字符。
③、处理*字符：当模式的第二个字符是*时，我们需要考虑两种情况：
- pattern.substring(2)：跳过这一部分的模式，因为可以表示它前面的字符出现0次（x）。
- text.substring(1)与pattern：如果当前字符匹配，则检查text的下一个字符，因为 * 可以表示多次。
④、其他情况：如果模式的第二个字符不是*，则需要当前字符匹配，并且剩余的字符串和模式也需要匹配。
来看代码：
class Solution {
// 基本情况：如果模式串为空，那么输入字符串也必须为空才匹配 if (pattern.isEmpty()) return text.isEmpty();
// 检查第一个字符是否匹配（考虑'.'的情况） boolean first_match = (!text.isEmpty() && (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
// 如果模式的下一个字符是'*' if (pattern.length() >= 2 && pattern.charAt(1) == '*'){ // 两种情况： // 1. 忽略模式中的这两个字符（'x*'），因为'*'可以表示前面的字符出现0次 // 2. 删除匹配的字符串中的一个字符（如果它能与模式中的'x'匹配），因为'*'可以表示多次 return (isMatch(text, pattern.substring(2)) || (first_match && isMatch(text.substring(1), pattern))); } else { // 如果下一个字符不是'*'，则直接比较当前字符，并递归处理剩余部分 return first_match && isMatch(text.substring(1), pattern.substring(1)); } }}
很容易懂，但很可惜效率不高，只能击败 5% 的用户。
分析 2
递归的效率很低，但是思路很清晰，那么我们能不能通过其他的方式来提高效率呢？
可以使用记忆法，也就是将已经计算过的结果存储起来，以避免重复计算，对于这道题，我们可以使用一个二维数组来作为缓存，来存储已经计算过的结果。
这样在递归调用中，如果遇到相同的子问题，我们可以直接从缓存中返回结果，而不是重新计算。
来看题解。
class Solution {
Boolean[][] memo;
public boolean isMatch(String text, String pattern) { // 初始化记忆矩阵，未计算的值为null memo = new Boolean[text.length() + 1][pattern.length() + 1]; // 从字符串和模式的开头开始递归匹配 return dp(0, 0, text, pattern); }
public boolean dp(int i, int j, String text, String pattern) { // 如果这个子问题已经计算过，则直接返回结果 if (memo[i][j] != null) { return memo[i][j]; } boolean ans; // 如果模式已经走到了末尾，返回text是否也走到了末尾 if (j == pattern.length()) { ans = i == text.length(); } else { // 检查text当前字符和pattern当前字符是否匹配 boolean first_match = (i < text.length() && (pattern.charAt(j) == text.charAt(i) || pattern.charAt(j) == '.'));
// 如果模式中下一个字符是'*' if (j + 1 < pattern.length() && pattern.charAt(j + 1) == '*') { // '*'匹配0次的情况 || '*'匹配1次或多次的情况 ans = (dp(i, j + 2, text, pattern) || first_match && dp(i + 1, j, text, pattern)); } else { // 如果下一个字符不是'*'，则继续递归检查下一个字符 ans = first_match && dp(i + 1, j + 1, text, pattern); } } // 计算完毕，存储结果 memo[i][j] = ans; return ans; }}
详细解释：
①、我们定义一个 memo 二维数组作为缓存。memo[i][j] 表示 text 从索引 i 开始的子串和 pattern 从索引 j 开始的子模式是否匹配。
②、isMatch 方法是解决问题的入口。
③、dp 方法是递归的核心，它接受 text 和 pattern 的索引 i 和 j。
④、在 dp 方法开始时，我们首先检查是否已经计算过当前的子问题。如果 memo[i][j] 不是 null，我们直接返回它的值。
⑤、如果模式 pattern 已经检查完毕 (j == pattern.length ())，则 text 也应该同时检查完毕 (i == text.length ())，这样才算匹配成功。
⑥、如果模式未检查完毕，我们首先确定 text 当前字符是否与 pattern 当前字符匹配。这里有两种情况：字符直接相等，或者 pattern 的字符是 .。
⑦、接下来，如果 pattern 中下一个字符是 *，我们有两个选择：
- 忽略 pattern 中的这两个字符（即 * 前面的字符和 *），因为 * 可以表示前面的字符出现0次。
- 如果 text 当前字符与 pattern 的 * 前面的字符匹配，我们可以继续递归地检查 text 的下一个字符，而 pattern 不变，因为 * 可以表示多次。
⑧、如果下一个字符不是 *，我们简单地递归调用下一个字符。
⑨、在递归结束时，我们将结果存储在 memo 中，并返回结果。
归通过存储子问题的结果来避免重复计算，这样，即使我们使用递归的方法，也能提高算法的效率。这种方法通常会将时间复杂度降低到接近动态规划的级别。
果不其然，效率飙升，击败 100% 的用户。
分析 3
**第 5 题 **的时候，我们就讲过动态规划了，那这道题其实用动态规划来做就非常合适。
我们先来看看动态规划的思路，然后再来看看怎么转移方程。
当然，让我按照您提出的结构来详细解释第二个题解的解题步骤。
1. 状态定义
我们定义一个二维布尔数组 dp，其中 dp[i][j] 表示字符串 text 的前 i 个字符与模式串 pattern 的前 j 个字符是否能够匹配。这里，i 和 j 分别代表 text 和 pattern 的子串长度。
2. 状态转移方程
状态转移是根据 pattern 的当前字符和它之前的字符来更新 dp 数组。以下是转移方程的详细说明：
①、当 pattern[j - 1] 是普通字符或 . 时，如果 pattern[j - 1] 等于 text[i - 1] 或者 pattern[j - 1] 是 .，则 dp[i][j] = dp[i - 1][j - 1]。这是因为当前字符匹配，所以匹配结果取决于剩余的子串。
②、当 pattern[j - 1] 是 '*' 时，有两种情况：
- 如果 '' 前的字符不匹配 text[i - 1]，即 pattern[j - 2] != text[i - 1] 且 pattern[j - 2] 不是 .，则 dp[i][j] = dp[i][j - 2]。这表示 '' 使得其前一个字符在 text 中出现 0 次。
- 如果 '' 前的字符匹配 text[i - 1] 或 pattern[j - 2] 是 .，则 dp[i][j] = dp[i][j - 2] || dp[i - 1][j]。这表示 '' 可以使得其前一个字符在 text 中出现 0 次或多次。
3. 初始状态
初始状态是动态规划的起点。我们需要正确地初始化 dp 数组：
- dp[0][0] = true; 表示两个空字符串能够匹配。
- 对于 pattern 中的每个字符，如果当前字符是 '*'，则需要检查它是否能使得 pattern 的这一部分与空字符串 text 匹配。如果是的话，则 dp[0][j] = dp[0][j - 2]。
4. 返回值
最终，dp[text.length ()][pattern.length ()] 的值表示整个字符串 text 是否与模式串 pattern 匹配。
来看代码：
class Solution {
// 状态定义：dp[i][j] 表示 text 的前 i 个字符和 pattern 的前 j 个字符是否匹配 boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1]; // 初始状态：空字符串是可以匹配的 dp[0][0] = true; for (int j = 2; j <= pattern.length(); j++) { if (pattern.charAt(j - 1) == '') { dp[0][j] = dp[0][j - 2]; } } // 状态转移方程 for (int i = 1; i <= text.length(); i++) { for (int j = 1; j <= pattern.length() ; j++) { if (pattern.charAt(j - 1) == '') { // 如果 pattern 的第 j 个字符是 ''，则需要考虑 pattern 的第 j - 1 个字符 pattern[j - 1] if (pattern.charAt(j - 2) == text.charAt(i - 1) || pattern.charAt(j - 2) == '.') { // 如果 pattern[j - 1] 为小写字母，那么 pattern[j - 1] 可以出现 0 次或多次 // 如果 pattern[j - 1] 为 '.'，那么 pattern[j - 1] 可以出现 0 次或多次 dp[i][j] = dp[i][j - 2] || dp[i - 1][j]; } else { // 如果 pattern[j - 1] 为 ''，那么 pattern[j - 1] 可以出现 0 次或多次 dp[i][j] = dp[i][j - 2]; } } else { // 如果 pattern 的第 j 个字符不是 '*'，则需要考虑 pattern 的第 j 个字符 pattern[j - 1] if (pattern.charAt(j - 1) == text.charAt(i - 1) || pattern.charAt(j - 1) == '.') { // 如果 pattern[j - 1] 为小写字母，那么 text[i - 1] 和 pattern[j - 1] 必须匹配 // 如果 pattern[j - 1] 为 '.'，那么 text[i - 1] 和 pattern[j - 1] 必须匹配 dp[i][j] = dp[i - 1][j - 1]; } } } } // 返回值 return dp[text.length()][pattern.length()]; }}
效率也不错。
总结
这道题的难度是困难，但是我们通过递归、记忆法、动态规划三种方式来循序渐进地解决，相信大家都能掌握了。
第一种方法最直观，基本上用到的知识也是 Java 基础当中必须要掌握的，比如说字符串的截取、字符串的比较等等。
推荐大家认真读一下二哥的 Java 进阶之路中字符串和数组相关的内容：
另外，关于动态规划，我也找了一个帖子供大家参考和学习：
视频的话，我也帮大家找了一个，讲的还不错。
力扣链接：https://leetcode.cn/problems/regular-expression-matching/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4200+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。
（优惠券仅 300 张，数量有限）
一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412