Drag image to reposition

正则表达式通配符匹配问题的 DP 解法和回溯解法对比

Created

July 21, 2022 4:24 PM

backtracking

dynamicProgramming

Description

本文介绍了正则表达式中通配符匹配问题的回溯解法和动态规划解法。回溯解法的思路是逐个字符匹配，对于 '*' 通配符则尝试匹配不同长度的子串。时间复杂度为指数级别。动态规划解法则是通过计算前缀匹配情况来判断是否匹配。时间复杂度大约为 O(N^2 M)。

Updated

July 16, 2023 5:58 AM

3 more properties

给定一文本字符串 std::string s, 以及一个 pattern 串 std::string p, 试判定 s 与 p 是否匹配。

假设文本串只被允许包含大小写英文字母，而 pattern 串除了大小写英文字母外还被允许包含字符类符号，在这些字符类符号中，’*’ 代表任意有限长的由大小写英文字母组成的字符串，’?’ 代表任意单个大小写英文字符；

所谓的「s 与 p 匹配」指的是：如果 p 全由大小写英文字母组成，那么 p 和 s 匹配当且仅当表达式 p == s 的求值结果为 true ;

若不然，若 p 中有 ‘*’ 或者 ‘?’ 这样的字符类，则我们说 p 与 s 是匹配的当且仅当能够对 p 中的 ‘*’ 与 ‘?’ 字符进行有限次替换使得 p == s.

对于有正则表达式应用经验的读者来说，’*’ 其实可以看作是「通配符」，能够匹配 0 长字符子串，也能够匹配任意有限长的字符子串，’?’ 也可以看作是通配符，只不过它相比于 ‘*’ 只能够匹配长度为 1 的字符子串。

以 std::string s = "aabca" , std::string p = "a*c?" 举例，我们可以让 p 的 '*' 替换为 "ab" , 再让 '?' 替换为 'a' , 从而将 p 替换为 "aabca" , 从而我们说 p 和 s 是匹配的。

以 std::string s = "cbbc", std::string p = "?**a" 举例，无论我们让 p 中的（两个）’*’ 被替换为何物，让 '?' 被替换何物，都无法从 p 得到 s, 这时我们可以说 p 和 s 是不匹配的。

上述的讨论除了帮助我们更明确地进一步理解问题本身之外，还向我们揭示了一个判定 p 与 s 是否匹配的思路：想象我们是在一个字符一个字符地扫描 p 中的字符（字符类）和 s 中的字符，指针 intptr_t i 指向 s 中正在被扫描到的字符，指针 intptr_t j 指向 p 中正在被扫描到的字符（字符类），若 p[j] 是大小写英文字母，则如果 s[i] == p[j], 就可以让 i, j 都自增，如果 p[j] == '?', 由于 '?' 匹配任何字符，所以也相当于 s[i] == p[j], 也自增 i 和 j, 如果 p[j] == '*', 我们就尝试让这个 '*' 分别匹配不同长度的 s 自 i 开始的 n 长子串，这个 n 可以分别尝试 0 到 N-i.

以下是 C++ 实现：

时间复杂度概览

以下 testcase 能够使得上列代码运行超时（LeetCode 报 TLE 错误）：

基本上，你可以理解为这样的解法它的时间复杂度是指数级别的。

正如代码里写的，当 p[j] 是 ‘*’ 的时候，程序就会去试一遍不同的 n, 当 p[j] 遇上第一个 '*' 的时候，会尝试 n1 个不同的 n 的取值，遇上第二个 '*' 的时候，会尝试 n2 次，遇上第三个 '*' 的时候，会尝试 n3 次，第四个的时候，会尝试 n4 次，那么

里面那段代码被指向的次数与 n1 * n2 * n3 * n4 大致成比例，当有 N 个 '*' 的时候，就是与 n1*n2*…*n_N 大致成比例，这就（不严格地）解释了为什么这样的回溯（穷举）算法的时间复杂度对于 'p' 中的 '*' 的数量来说是指数级别的。

动态规划解法

前缀匹配判定函数

考虑这样一个函数：

它返回的是：s 的 sPrefixLen 长度的前缀与 p 的 pPrefixLen 长度的前缀是否匹配。

为了方便起见，我们将它写为：

而 char *s 和 char *p 则作为外层变量出现。

容易验证，函数 isPrefixMatch 有下列性质：

isPrefixMatch(0, 0) == true ; 理解为：空串总是和空 pattern 匹配；

若 p[pPrefixLen-1]=='*', 并且存在非负整数 n0 使得 isPrefixMatch(n0, pPrefixLen-1) 为 true, 那么对一切 n0 ≤ n ≤ N 都有 isPrefixMatch(n, nPrefixLen) 成立；

若 p[nPrefixLen-1]=='?', 并且 isPrefixMatch(sPrefixLen-1, pPrefixLen-1) 且 sPrefixLen ≤ N, 那么 isPrefixMatch(sPrefixLen, pPrefixLen) 成立；

若 p[nPrefixLen-1] 既不是 '*' 也不是 '?', 则 isPrefixMatch(sPrefixLen, pPrefixLen) 成立的条件是性质 3 的条件再加上一条：s[sPrefixLen-1] == p[pPrefixLen-1].

函数 isPrefixMatch 的 4 条性质也向我们揭示了如何去计算它，我们知道，isPrefixMatch(…, j) 一般都依赖于 isPrefixMatch(…, j-1), 所以，我们可以先把 isPrefixMatch(…, j-1) 计算出来，再去计算 isPrefixMatch(…, j), 这样做，可以减少许多不必要的重复计算。

除此之外，我们还知道，s 与 p 是否匹配等价于 isPrefixMatch(s.data(), p.data(), s.size(), p.size()).

以下代码计算出函数 isPrefixMatch 对于每一个输入 (i,j) 的答案并且将它们存储在一个二阶数组里面，N 和 M 分别为 s 串和 p 串的长度：

直观来看，for 循环的最大深度只有 3 层，因此我们可以估计该算法的时间复杂度大约是立方级别的，大约是 O(N^2 M).

示例运行结果见：https://leetcode.com/submissions/detail/751980289/

正则表达式通配符匹配问题的 DP 解法和回溯解法对比

正则表达式通配符匹配问题的 DP 解法和回溯解法对比

时间复杂度概览

动态规划解法

前缀匹配判定函数

Recommend

正则表达式匹配任意字符（包括换行符）

用Pike's VM实现的非回溯正则表达式引擎

正则表达式量词匹配方式的讲解（上篇）

PHP中正则表达式对UNICODE字符码的匹配

正则表达式匹配素数的原理讲解

小议正则表达式效率：贪婪、非贪婪与回溯

PHP正则表达式的效率：回溯与固化分组

第四章正则表达式回溯法原理

正则表达式匹配问题 - Grey Zeng

Java处理正则匹配卡死（正则回溯问题） - coffeebabe

About Joyk