经典 Regular Expression Matching 问题中，Pattern 包含普通字符以及：
. → 任意单个字符
* → 前一个元素出现零次或多次
例如：
s = "aa"
p = "a*"
结果为 true。
Dot
. 可以匹配任意一个字符。
例如：
c.t
可以匹配 cat、cut 和 c9t。
Star
* 作用于前一个 Pattern Element。
a*
可以匹配空字符串、a、aa、aaa 等。
为什么使用动态规划？
Star 会产生多个选择：使用前一个元素零次、一次或多次。
这些选择会反复产生相同子问题，因此适合使用 Dynamic Programming 或 Memoization。
DP 状态
定义：
dp[i][j]
表示 String 前 i 个字符是否能够完整匹配 Pattern 前 j 个字符。
dp[0][0] = true
像 a*b*c* 这样的 Pattern 可以匹配空字符串。
普通字符或 Dot
如果当前字符相同，或者 Pattern 当前字符是 .：
dp[i][j] = dp[i - 1][j - 1]
Star
第一种情况是不使用前一个元素：
dp[i][j] = dp[i][j - 2]
如果前一个 Pattern 元素与当前 String 字符匹配，则 Star 可以继续 Consume：
dp[i][j] = dp[i][j] || dp[i - 1][j]
TypeScript 实现
function isRegexMatch(s: string, p: string): boolean {
const dp = Array.from(
{ length: s.length + 1 },
() => new Array(p.length + 1).fill(false)
);
dp[0][0] = true;
for (let j = 2; j <= p.length; j++) {
if (p[j - 1] === '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (let i = 1; i <= s.length; i++) {
for (let j = 1; j <= p.length; j++) {
if (
p[j - 1] === '.' ||
p[j - 1] === s[i - 1]
) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 2];
if (
p[j - 2] === '.' ||
p[j - 2] === s[i - 1]
) {
dp[i][j] =
dp[i][j] || dp[i - 1][j];
}
}
}
}
return dp[s.length][p.length];
}
复杂度
Time Complexity: O(n × m)
Space Complexity: O(n × m)
Memoization
递归解法中，当遇到 x* 时有两个主要选择：
跳过 x*
或者在当前字符匹配时：
Consume 一个字符并继续保留 x*
如果没有 Memoization，会重复计算大量相同状态。
Regex 与 Wildcard Matching
Regex 中：
. → 任意一个字符
* → 重复前一个元素
Wildcard 中通常是：
? → 任意一个字符
* → 任意字符序列
所以 * 的意义不同。
Full Match
这里要求 Pattern 匹配整个 String。
因此：
hello
ell
结果为 false，尽管 ell 是其中的 Substring。
实际 Regex
生产系统中的 Regex 通常用于：
- Validation
- Search
- Log Filtering
- Data Extraction
- Text Processing
应用代码通常应该使用成熟的 Regex Engine，而不是自己实现完整 Regex 引擎。
安全与性能
一些 Backtracking Regex Engine 在特殊 Pattern 和输入组合下可能产生严重性能问题，这类风险常与 ReDoS 有关。
因此理解 Regex 的复杂度对生产系统同样重要。
技术面试重点
需要理解：
.的意义。*依赖前一个元素。- DP State 定义。
- Empty String 初始化。
- Star 的零次和多次使用。
O(n × m)复杂度。
常见错误
- 把
*当作独立通配符。 - 认为
*只能出现零次或一次。 - 忘记 Empty String。
- 把 Substring Match 当作 Full Match。
总结
Regular Expression Matching 是将递归 Branching 转换为 Dynamic Programming 的经典问题。
. → 任意一个字符
x* → x 出现零次或多次
标准 DP 解法复杂度为：
Time: O(n × m)
Space: O(n × m)