企业官网建设流程全解析

LeetCode 每日一题：10. Regular Expression Matching 正则匹配的动态规划解法

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文基于本仓库"每日一题"活动中的 2019-06-09 记录 展开，系统讲解 LeetCode 第 10 题 Regular Expression Matching 的完整求解过程。这道题同时被标记为String、Dynamic Programming、Backtracking三类 tag，是字符串类动态规划的经典代表。读完本文，你将掌握".与*通配正则匹配"的状态定义方法、转移方程推导思路，以及它与编辑距离类问题的共通套路，并能直接复用文中给出的可运行 Java 实现。

信息卡片

• 时间：2019-06-09（来源：每日一题历史汇总，编号为第 10 题的每日一题记录）
• 难度类型：Hard
• tag：String、Dynamic Programming、Backtracking

在仓库的 daily/README.md 中，这道题被收录为每日一题活动的历史题目之一，记录了"大家一起解一道题、讨论更集中、日后筛选进入题解模块"的活动机制，其内容格式遵循 每日一题模板 中规定的"信息卡片 + 题目描述 + 参考答案 + 其他优秀解答"结构。

题目描述

给定一个输入字符串s和一个模式串p，实现一个支持.和*的正则表达式匹配：

• .匹配任意单个字符。
• *匹配零个或多个前面的元素。

匹配必须覆盖整个输入字符串（而非部分匹配）。

注意：

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

示例

示例 1

Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".

示例 2

Input: s = "aa" p = "a*" Output: true Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

示例 3

Input: s = "ab" p = ".*" Output: true Explanation: ".*" means "zero or more (*) of any character (.)".

示例 4

Input: s = "aab" p = "c*a*b" Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

示例 5

Input: s = "mississippi" p = "mis*is*p*." Output: false

本题要求判断给出的字符串和对应的正则是否匹配，匹配返回true，否则返回false。

思路剖析：为什么是动态规划

从题目本身来看，最容易想到的"作弊"手段是直接调用语言内置的正则匹配 API。例如使用 Java 字符串的matches方法即可一步通过本题（详见下文"扩展讨论"一节）。但本题的正解需要老老实实地手写匹配逻辑，此时动态规划是首选方案。

原文档明确指出：基本思路是考察s和p任意从头到某两个字符之间的匹配程度，这与编辑距离（Edit Distance）那道题非常相似。编辑距离的经典做法是定义dp[i][j]表示两个字符串前缀之间的转换代价；本题同样是双序列问题，因此可以套用同一套路——用dp[i][j]表示s的前i个字符与p的前j个字符的匹配程度。

这一"双字符串前缀状态"的定义方式，在仓库的 动态规划专题文章 中有专门归纳：

两个字符串的状态，通常是dp[i][j]表示字符串 s1 以 i 结尾，s2 以 j 结尾的 ...。

本题正是该套路最典型的应用之一。同时该专题还强调，动态规划问题的两个核心性质是：

• 最优子结构：问题的最优解所包含的子问题的解也是最优的；
• 无后效性：子问题的解一旦确定，就不再受之后决策的影响。

对于正则匹配而言，dp[i][j]只依赖更小规模的子问题（前缀更短的i-1、j-1、j-2），不存在回头依赖更大规模子问题的可能，因此天然满足无后效性，可以放心使用自底向上的填表法。

核心解法：二维动态规划

状态定义

dp[i][j] 代表 s 的前 i 位字符和 p 的前 j 位字符的匹配程度（布尔值）

例如dp[1][2]代表s的第一个字符和p的前两个字符的匹配结果。

转移方程推导

逐字符比较s的第i个字符与p的第j个字符，分两大类情况：

情况一：p[j-1]为普通字符或.

如果p的第j个字符等于s的第i个字符，或者p的第j个字符是.（可匹配任意单个字符），那么当前两个字符直接抵消，匹配结果完全取决于各自前一个字符的状态：

dp[i][j] = dp[i - 1][j - 1]

情况二：p[j-1]为*

*通配的是它前面的那个元素（即p的第j-1个字符），因此必须考虑p的第j-1个字符能否匹配上s的第i个字符：

1. 根本匹配不了：p的第j-1个字符既不是.，也不等于s的第i个字符。此时*只能匹配零个前面的元素，即把p中"字符 +*"这一组整体丢弃：

   dp[i][j] = dp[i][j - 2]

2. 可以匹配：p的第j-1个字符是.，或者与s的第i个字符相同。此时*可以匹配 0 个、1 个或 n 个s的第i个字符，三种情况取"或"：

   dp[i][j] = dp[i][j - 2] // 0 个：整体丢弃 "字符*" 这一组 || dp[i][j - 1] // 1 个：匹配一次，p 退一位 || dp[i - 1][j] // n 个：继续匹配 s 的前一个字符

其中n 个（dp[i - 1][j]）最不好理解，可以这样想：我能匹配你 n 个，肯定说明我已经匹配掉了你前面的 n-1 个，即s的前i-1个字符与p的前j个字符已经匹配成功，也就是dp[i - 1][j]。

初始化

• dp[0][0] = true：空字符串与空模式天然匹配。

• 第一行的初始化需要单独处理：s为空时，p中形如a*、c*a*这样的组合可以通过"匹配零个"来消掉。因此当p的第j个字符是*且dp[0][j-2]为true时，dp[0][j] = true：

  for (int j = 2; j <= p.length(); j++) { if (p.charAt(j - 1) == '*' && dp[0][j - 2]) dp[0][j] = true; }

完整参考代码（Java）

以下代码完整继承自 daily/2019-06-09.md 的参考答案，保留了原文档的逐行思路注释：

class Solution { public boolean isMatch(String s, String p) { if (s == null || p == null) return false; // dp[i][j]代表s的前i位字符和p的前j位字符的匹配程度 // dp[1][2]代表s的第一个字符和p的前两个字符的匹配 // 如果s的第i个字符和p的第j相等或者j为.那么dp[i][j]的匹配程度取决于dp[i - 1][j - 1] // 如果p的第j个字符为*，那么就要考虑*匹配0个，1个，n个s的第i个字符的情况，以及根本匹配不了的情况 // 根本匹配不了的意思是指p的j - 1个字符和s的第i个字符不相同，此时的匹配情况是dp[i][j] = dp[i][j - 2] // 然后是p的第j - 1个字符是.或者和s的i个字符相同的情况，此时可以匹配0 1 个n个s的第i个字符 // 0个: dp[i][j] = dp[i][j - 2] // 1个: dp[i][j] = dp[i - 1][j - 1] // n个: dp[i][j] = dp[i - 1][j] // n个的最不好理解，可以按照下面的想 // 我能匹配你n个，我肯定匹配了你前面的n-1个，也就是dp[i - 1][j] // 最后的结果是dp[s.length()][p.length()] boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; dp[0][0] = true; for (int j = 2; j <= p.length(); j++) { if (p.charAt(j - 1) == '*' && dp[0][j - 2]) dp[0][j] = true; } for (int i = 1; i <= s.length(); i++) { for (int j = 1; j <= p.length(); j++) { if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else if (p.charAt(j - 1) == '*') { if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') { dp[i][j] = dp[i][j - 2]; } else { dp[i][j] = (dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j]); } } } } return dp[s.length()][p.length()]; } }

复杂度分析

• 时间复杂度：双重循环遍历整个(s.length() + 1) × (p.length() + 1)的 DP 表，每次转移为O(1)，总复杂度为O(m × n)，其中m = s.length()，n = p.length()。
• 空间复杂度：使用二维布尔数组，为O(m × n)。

如果希望进一步优化空间，可以观察到第i行的转移只依赖第i-1行与当前行，因此可以用滚动数组将空间压缩到O(n)，但需要注意dp[i][j-2]、dp[i][j-1]与dp[i-1][j]三个来源在滚动时的取值顺序，避免覆盖未使用完的旧值。

用示例验证状态转移

以示例 4（s = "aab"，p = "c*a*b"，预期结果为true）为例，手动走一遍关键路径：

1. dp[0][0] = true；
2. 初始化第一行：p[1] = 'c'、p[2] = '*'，dp[0][2] = dp[0][0] = true，即c*匹配零个c；同理dp[0][4] = dp[0][2] = true，即c*a*可匹配零个字符；
3. 匹配s的第一个'a'：p[4] = 'a'与s[1]相同，dp[1][4] = dp[0][3]，而dp[0][3]为 false（p前三个字符c*a无法匹配空串），于是转向p[5] = '*'分支：p[4] = 'a'与s[1]相同，dp[1][5] = dp[1][3] || dp[1][4] || dp[0][5] = false || false || true = true（a*匹配一个a，前面c*匹配零个c）；
4. 类似地，第二个'a'由a*匹配第二个（dp[i-1][j]分支），'b'由最后的'b'匹配；
5. 最终dp[3][5] = true，判定匹配成功。

这个手算过程可以直观感受到：dp[i-1][j]这一分支正是*连续吞噬多个相同字符的机制所在。

从回溯视角理解本题

题目 tag 中还包含Backtracking。仓库的 回溯专题文章 指出：回溯的本质是穷举所有可能，采用"试错"思想分步解决问题，走不通就回头撤销上一步的选择。本题的朴素递归解法正是回溯思路：逐个字符尝试匹配，遇到*时穷举"匹配 0 次、1 次、多次"的所有分支，只要有一个分支能走到两个字符串同时耗尽，即返回true。

然而朴素回溯在形如"aaaaaaaaaaaaaaaaaaaaab"与"a*a*a*...b"的输入下会产生大量重复子问题，是指数级的复杂度；这也正是"如果存在重叠子问题，就是使用记忆化递归（或动态规划）解题的强有力信号"（见 动态规划专题）。因此，将回溯递归加上备忘录（memoization），把(i, j)参数对作为 key 缓存结果，就自然演化为本文的 DP 填表法——两者在本质上共享同一套状态划分，DP 只是把递归的自顶向下换成了自底向上的迭代。

扩展讨论

API 作弊解法

原文档提到：如果仅仅追求通过题目，可以直接使用语言内置的正则匹配 API。例如 Java 中：

class Solution { public boolean isMatch(String s, String p) { return s.matches(p); } }

需要注意，这依赖具体语言的正则语义与 LeetCode 该题定义（.匹配任意字符、*匹配前一个元素的零次或多次）恰好一致的前提，作为刷题思路不可取，但可以作为验证 DP 实现正确性的对照手段。

与编辑距离类问题的共性

本题与编辑距离、最长公共子序列（LCS）等题目共享同一类模型：双序列前缀 DP。这类问题的通用三步走是：

1. 定义dp[i][j]为两个序列前缀的某种关系（匹配与否 / 距离 / 长度）；
2. 按"当前字符是否相等"分类讨论转移；
3. 答案收敛在dp[m][n]。

仓库中同类型的 DP 题目还包括 5. 最长回文子串、516. 最长回文子序列、62. 不同路径、416. 分割等和子集 等，可以在练习时相互对照、总结状态定义套路。

边界情况清单

• s = ""、p = ""→true（dp[0][0]）；
• s = ""、p = "a*"→true（*匹配零个）；
• s = ""、p = "a"→false；
• p中连续出现多个*组合（如a*b*）——题目约定*前必有可作用字符，按*分组处理即可；
• 两个字符串都为null时，代码开头直接返回false。

总结

Regular Expression Matching 是双序列动态规划的经典题目，核心收获有三点：

1. 状态定义套路：双字符串问题优先考虑dp[i][j]表示两个前缀的匹配关系；
2. *的三种转移：匹配 0 个（dp[i][j-2]）、1 个（dp[i][j-1]）、n 个（dp[i-1][j]），其中 n 个分支最难理解也最关键；
3. 与回溯、记忆化递归的统一：回溯穷举 + 备忘录剪枝，与自底向上的 DP 填表殊途同归。

本文的题解原始记录位于 daily/2019-06-09.md，方法论支撑可继续阅读仓库的 动态规划专题 与 回溯专题，每日一题活动整体背景见 daily/README.md。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode