正则表达式匹配问题（带字符类和量词）

字数 2419 2025-12-02 04:41:14

正则表达式匹配问题（带字符类和量词）

题目描述
给定一个字符串 s 和一个模式 p，模式中可能包含以下特殊字符：

.：匹配任意单个字符。
*：匹配零个或多个前面的元素。
[abc]：字符类，匹配 a、b 或 c 中的任意一个字符。
{n}：量词，匹配前面的元素恰好 n 次（n 为正整数）。
{n,}：匹配前面的元素至少 n 次。
{n,m}：匹配前面的元素至少 n 次，至多 m 次。

请实现一个函数，判断字符串 s 是否完全匹配模式 p（即整个 s 需被 p 覆盖）。例如：

输入 s = "aab", p = "c*a*b" 返回 true（* 匹配零个 c 和两个 a）。
输入 s = "abc", p = "a[bc]{2}" 返回 true（[bc] 匹配 b 和 c，{2} 表示匹配两次）。

解题过程

步骤1：问题分析
本题是经典正则表达式匹配的扩展，需处理字符类（如 [abc]）和量词（如 {n}）。核心难点在于量词可能匹配可变长度的子串，需动态规划逐段检查匹配情况。

关键思路
使用区间动态规划，定义 dp[i][j] 表示 s 的前 i 个字符是否匹配 p 的前 j 个字符。需根据 p 中字符的类型（普通字符、.、字符类、量词）设计状态转移。

步骤2：预处理模式字符串
将模式 p 解析为更易处理的结构。例如：

将 [abc] 转换为字符集合 {a, b, c}。
将 a{2,3} 转换为量词结构 (a, min=2, max=3)。

为简化，我们假设模式已预处理为列表 patterns，每个元素为：

普通字符（如 'a'）
通配符 '.'
字符类（如 {'a','b','c'}）
量词结构 (base_pattern, min_count, max_count)，其中 base_pattern 是单个字符、字符类或 .。

步骤3：定义DP状态
设 dp[i][j] 表示 s[0:i]（长度为 i 的前缀）是否匹配 patterns[0:j]（前 j 个模式单元）。
初始状态：

dp[0][0] = true：空字符串匹配空模式。
若 patterns 开头有可匹配零次的量词（如 a*），则 dp[0][j] 可能为 true。

步骤4：状态转移方程
遍历 i 从 0 到 n（n 为 s 长度），j 从 1 到 m（m 为 patterns 长度），分情况讨论：

情况1：当前模式单元为普通字符或字符类

若 i > 0 且 s[i-1] 匹配当前模式单元（即字符相等、或模式为 .、或字符类包含 s[i-1]），则：
dp[i][j] = dp[i-1][j-1]。

情况2：当前模式单元为量词 (base, min, max)
需检查量词匹配 k 次的情况（k 从 min 到 max）：

若 k = 0：直接跳过该量词，dp[i][j] = dp[i][j-1]。
若 k > 0：要求 s 的最后 k 个字符均匹配 base，且剩余部分匹配前序模式：
dp[i][j] = dp[i-k][j-1] && (s[i-k:i] 匹配 base 重复 k 次)。
注意 k 不能超过 i，且需逐字符检查匹配。

步骤5：匹配检查的辅助函数
为实现量词匹配，需函数 match_range(s, start, end, base) 判断 s[start:end] 是否匹配 base 重复 (end-start) 次：

若 base 为普通字符：检查 s[start:end] 是否全为该字符。
若 base 为 .：任意字符均匹配。
若 base 为字符类：检查每个字符是否在集合内。

步骤6：算法实现示例
以 s = "abc", p = "a[bc]{2}" 为例：

解析 patterns：['a', {'b','c'}, (base={'b','c'}, min=2, max=2)]（实际中需合并相邻相同模式，此处简化为独立单元）。
初始化 dp[0][0]=true。
匹配 'a'：dp[1][1] = dp[0][0] && s[0]=='a' → true。
匹配 [bc]：dp[2][2] = dp[1][1] && s[1] in {'b','c'} → true（s[1]='b'）。
匹配 {2}：实际已匹配两次 [bc]，但模式中 {2} 对应重复前一个单元。需调整解析逻辑，将 [bc]{2} 视为一个模式单元 (base=[bc], min=2, max=2)，直接检查 s 的最后 2 字符是否匹配：
- i=3, j=3：k=2，检查 s[1:3]="bc" 是否匹配 base 两次 → 是，且 dp[1][2] 需为 true（此处需注意模式索引调整）。

步骤7：复杂度优化

直接枚举 k 可能使复杂度达 O(n²·m)。可通过预处理快速判断字符段匹配，或使用贪心匹配最大可能次数来优化。
实际中常将量词转换为回溯或 NFA 自动机，但区间DP提供了一种直观的结构化思路。

总结
本题通过扩展经典正则匹配的DP框架，加入对字符类和量词的处理，体现了区间动态规划在模式匹配中的灵活性。关键点在于将模式解析为原子单元，并设计量词匹配的多次数检查机制。

正则表达式匹配问题（带字符类和量词）题目描述给定一个字符串 s 和一个模式 p ，模式中可能包含以下特殊字符： . ：匹配任意单个字符。 * ：匹配零个或多个前面的元素。 [abc] ：字符类，匹配 a 、 b 或 c 中的任意一个字符。 {n} ：量词，匹配前面的元素恰好 n 次（ n 为正整数）。 {n,} ：匹配前面的元素至少 n 次。 {n,m} ：匹配前面的元素至少 n 次，至多 m 次。请实现一个函数，判断字符串 s 是否完全匹配模式 p （即整个 s 需被 p 覆盖）。例如：输入 s = "aab" , p = "c*a*b" 返回 true （ * 匹配零个 c 和两个 a ）。输入 s = "abc" , p = "a[bc]{2}" 返回 true （ [bc] 匹配 b 和 c ， {2} 表示匹配两次）。解题过程步骤1：问题分析本题是经典正则表达式匹配的扩展，需处理字符类（如 [abc] ）和量词（如 {n} ）。核心难点在于量词可能匹配可变长度的子串，需动态规划逐段检查匹配情况。关键思路使用区间动态规划，定义 dp[i][j] 表示 s 的前 i 个字符是否匹配 p 的前 j 个字符。需根据 p 中字符的类型（普通字符、 . 、字符类、量词）设计状态转移。步骤2：预处理模式字符串将模式 p 解析为更易处理的结构。例如：将 [abc] 转换为字符集合 {a, b, c} 。将 a{2,3} 转换为量词结构 (a, min=2, max=3) 。为简化，我们假设模式已预处理为列表 patterns ，每个元素为：普通字符（如 'a' ）通配符 '.' 字符类（如 {'a','b','c'} ）量词结构 (base_pattern, min_count, max_count) ，其中 base_pattern 是单个字符、字符类或 . 。步骤3：定义DP状态设 dp[i][j] 表示 s[0:i] （长度为 i 的前缀）是否匹配 patterns[0:j] （前 j 个模式单元）。初始状态： dp[0][0] = true ：空字符串匹配空模式。若 patterns 开头有可匹配零次的量词（如 a* ），则 dp[0][j] 可能为 true 。步骤4：状态转移方程遍历 i 从 0 到 n （ n 为 s 长度）， j 从 1 到 m （ m 为 patterns 长度），分情况讨论：情况1：当前模式单元为普通字符或字符类若 i > 0 且 s[i-1] 匹配当前模式单元（即字符相等、或模式为 . 、或字符类包含 s[i-1] ），则： dp[i][j] = dp[i-1][j-1] 。情况2：当前模式单元为量词 (base, min, max) 需检查量词匹配 k 次的情况（ k 从 min 到 max ）：若 k = 0 ：直接跳过该量词， dp[i][j] = dp[i][j-1] 。若 k > 0 ：要求 s 的最后 k 个字符均匹配 base ，且剩余部分匹配前序模式： dp[i][j] = dp[i-k][j-1] && (s[i-k:i] 匹配 base 重复 k 次) 。注意 k 不能超过 i ，且需逐字符检查匹配。步骤5：匹配检查的辅助函数为实现量词匹配，需函数 match_range(s, start, end, base) 判断 s[start:end] 是否匹配 base 重复 (end-start) 次：若 base 为普通字符：检查 s[start:end] 是否全为该字符。若 base 为 . ：任意字符均匹配。若 base 为字符类：检查每个字符是否在集合内。步骤6：算法实现示例以 s = "abc" , p = "a[bc]{2}" 为例：解析 patterns ： ['a', {'b','c'}, (base={'b','c'}, min=2, max=2)] （实际中需合并相邻相同模式，此处简化为独立单元）。初始化 dp[0][0]=true 。匹配 'a' ： dp[1][1] = dp[0][0] && s[0]=='a' → true 。匹配 [bc] ： dp[2][2] = dp[1][1] && s[1] in {'b','c'} → true （ s[1]='b' ）。匹配 {2} ：实际已匹配两次 [bc] ，但模式中 {2} 对应重复前一个单元。需调整解析逻辑，将 [bc]{2} 视为一个模式单元 (base=[bc], min=2, max=2) ，直接检查 s 的最后 2 字符是否匹配： i=3 , j=3 ： k=2 ，检查 s[1:3]="bc" 是否匹配 base 两次 → 是，且 dp[1][2] 需为 true （此处需注意模式索引调整）。步骤7：复杂度优化直接枚举 k 可能使复杂度达 O(n²·m)。可通过预处理快速判断字符段匹配，或使用贪心匹配最大可能次数来优化。实际中常将量词转换为回溯或 NFA 自动机，但区间DP提供了一种直观的结构化思路。总结本题通过扩展经典正则匹配的DP框架，加入对字符类和量词的处理，体现了区间动态规划在模式匹配中的灵活性。关键点在于将模式解析为原子单元，并设计量词匹配的多次数检查机制。