10、正则表达式匹配

题意

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

• ‘.’ 匹配任意单个字符

• ’*’ 匹配零个或多个前面的那一个字符

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

示例

输入：s = "aa", p = "a"

输出：false

解释："a" 无法匹配 "aa" 整个字符串。

输入：s = "aa", p = "a*"

输出：true

解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 前面的字符是 'a'，因此，字符串

"aa" 可被视为 'a' 重复了一次。

输入：s = "ab", p = ".*"

输出：true

解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示

• 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

大致了解正则表达式是什么，有什么作用后，对这道题会有更清晰的解题思路。

一句话总结下：正则表达式就是一种用来匹配字符串的规则。

010.%E6%AD%A3%E5%88%99%E5%BC%8F%E5%8C%B9%E9%85%8D-20240117143512

.png

上面是一个比较简单的正则表达式，具体解释如下：

• ^：匹配输入字符串的开始位置。

• [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 {

public boolean isMatch(String text, String pattern) {

// 基本情况：如果模式串为空，那么输入字符串也必须为空才匹配

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% 的用户。

010.%E6%AD%A3%E5%88%99%E5%BC%8F%E5%8C%B9%E9%85%8D-20240117154804

.png

分析 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 中，并返回结果。

归通过存储子问题的结果来避免重复计算，这样，即使我们使用递归的方法，也能提高算

法的效率。这种方法通常会将时间复杂度降低到接近动态规划的级别。

010.%E6%AD%A3%E5%88%99%E5%BC%8F%E5%8C%B9%E9%85%8D-20240117195839

.png

果不其然，效率飙升，击败 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 {

public boolean isMatch(String text, String pattern) {

// 状态定义：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()];

}

}

效率也不错。

010.%E6%AD%A3%E5%88%99%E5%BC%8F%E5%8C%B9%E9%85%8D-20240117204741

.png

总结

这道题的难度是困难，但是我们通过递归、记忆法、动态规划三种方式来循序渐进地解

决，相信大家都能掌握了。

第一种方法最直观，基本上用到的知识也是 Java 基础当中必须要掌握的，比如说字符串

的截取、字符串的比较等等。

推荐大家认真读一下二哥的 Java 进阶之路中字符串和数组相关的内容：

• String 类

• 数组

另外，关于动态规划，我也找了一个帖子供大家参考和学习：

• 动态规划算法详解

• 动态规划基础知识

• 动态规划解题套路框架

视频的话，我也帮大家找了一个，讲的还不错。

• 10 分钟彻底搞懂“动态规划”算法

力扣链接：https://leetcode.cn/problems/regular-expression-matching/