infabc

这个屌丝很懒，什么也没留下！

热门标签

刷题：动态规划（DP）之正则表达式匹配_正则表达式匹配动态规划

作者：infabc | 2024-01-31 14:24:01

踩

正则表达式匹配动态规划

力扣

拓展：

题号	题解	难度
本题：正则化匹配	状态转移推导+滚动优化+提前结束	困难
剑指offer 19.正则表达式匹配	状态转移推导+滚动优化+提前结束	困难
44.通配符匹配	状态转移推导+滚动优化+提前结束	困难
72.编辑距离	字符串DP解决一众字符匹配问题	困难
115.不同的子序列	记忆化搜索、动态规划+滚动数组优化	困难
583.两个字符串的删除操作	字符串DP解决一众字符匹配问题	困难
1143.最长公共子序列	字符串DP解决一众字符匹配问题	困难

动态规划，可解决一众字符串匹配问题：

解题思路：动态规划

一. 状态定义
定义 dp[i][j] 表示 s 的前 i个字符和 p的前 j 个字符能否匹配。

二.状态转移

在进行状态转移时，s中的字符是固定不变的，我们考虑p的第j个字符与s的匹配情况：

1. $p[j]$ 是一个小写字母a-z，则 $s[i]$ 必须也为同样的小写字母方能完成匹配：

$dp[i][j] = \left\{\begin{matrix}dp[i-1][j-1], & s[j] = p[j]\\ false& s[j] \neq p[j] \end{matrix}\right.$

2. $p[j] = '.'$ ，则 $p[j]$ 一定可以与 $s[i]$ 匹配成功，此时有

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

3. $p[j] = '*'$ ，则表示可对 $p[j]$ 的前一个字符 $p[j-1]$ 匹配（或理解为复制）任意次（包括 00 次）。为便于阐述，以下图 $s="abaaacd"$ ， $p = "aba*cd"$ ， $s[i] = 'a'$ ， $p[j-1] = 'a'$ 和 $p[j] = '*'$ 为例进行说明：

》匹配 0次，意味着 $p[j-1]$ 和 $p[j]$ 不起作用，相当于在中删去了 $p[j-1]$ 和 $p[j]$ ，此时有：

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

》匹配 1 次，意味着 $p[j-1]$ 和 $p[j]$ 组成了'a'，若 $s[i] = p[j-1]$ ，则 $dp[i][j]$ 可由 $dp[i-1][j-2]$ 转移而来，此时有：

$dp[i][j] = dp[i-1][j-2], \delta s[i] = p[j-1]$

》匹配 2 次，意味着 $p[j-1]$ 和 $p[j]$ 组成了'aa'，若 $s[i-1,i] = p[j-1]$ ，则 $dp[i][j]$ 可由 $d[i-2][j-2]$ 转移而来，此时有：

$d[i][j] = dp[i-2][j-2], \delta s[i-1, i] = p[j-1].$

》匹配 3 次，意味着 $p[j-1]$ 和 $p[j]$ 组成了'aaa'，若 $s[i-2,i-1,i] = p[j-1]$ ，则 $dp[i][j]$ 可由 $dp[i-3][j-2]$ 转移而来，此时有：

$d[i][j] = dp[i-3][j-2], \delta s[i-2,i-1,i] = p[j-1]$

.......

》匹配 k次，意味着 $p[j-1]$ 和 $p[j]$ 组成了k个'a'，若 $s[i-k+1,i-k+2,...,i] = p[j-1]$ ，则 $dp[i][j]$ 可由 $dp[i-k][j-2]$ 转移而来，此时有：

$dp[i][j] = dp[i-k][j-2],\delta s[i-k+1,...,i] = p[j-1]$

上述过程对应的状态更新过程如下图所示：

状态转移的优化：总的来看，当 $p[j] = '*'$ 时，对于匹配0～k次,我们有：

$\begin{align*} (1) dp[i][j] = dp[i][j-2] \ or \ {\color{Red} dp[i-1][j-2] \&\ s[i] = p[j-1] }\ or & &\\ {\color{Blue} dp[i-2][j-2] \&\ s[i-1, i] = p[j-1]} \ or \ ... \ or \ &\\ {\color{Green} dp[i-k][j-2] \&\ s[i-k+1,...,i] = p[j-1] }\end{align*}$

同时，对于 $dp[i-1][j]$ 我们有：

$\begin{align*} (2) dp[i-1][j] = {\color{Red} dp[i-1][j-2] }\ or \ & &\\ {\color{Blue} dp[i-2][j-2] \&\ s[i-1, i] = p[j-1]} \ or \ ... \ or \ &\\ {\color{Green} dp[i-k][j-2] \&\ s[i-k+1,...,i] = p[j-1] }\end{align*}$

观察发现，（2）式与（1）式中的后k项刚好相差了一个条件$\mathbf{{\color{Red} s[i] = p[j-1]}\$,将(2)式代入（1）式可得简化后的 状态转移方程 为：

$dp[i][j] = dp[i][j-2] or \begin{Bmatrix} dp[{\color{Red} i-1}][j]& \&\ s[i] = p[j-1] \end{Bmatrix}$

$p[j] = '*'$ 时，简化后对应的状态更新过程如下图所示：

需要特别注意的是：若 $p[j-1] = '.'$ ,此时 $p[j-1]$ 可表示任意字符，显然也就满足 $s[i] = p[j-1]$

以上状态转移的空间优化与「完全背包问题」的极为相似，感兴趣的读者可参考题目 322. 零钱兑换 以及对应的状态转移公式的优化推导 题解：从0-1背包到完全背包，逐层深入+推导。

总结以上各种情况来看，最终的状态转移方程如下：

$(4) dp[i][j] = \left\{\begin{matrix} dp[i-1][j-1], & s[i] = p[j] \\ dp[i][j-2],& p[j] = '*' \&\ s[i] \neq p[j-1] \\ dp[i-1][j],& p[j] = '*' \&\ s[i] = p[j-1] \end{matrix}\right.$

由于空间限制，上述判断中未展示 $p[j] = '.'$ 的情况。事实上，当 $p[j] = '.'$ 时我们认为 $s[i] = p[j]$ 。

从坐标的角度来看，对应的状态更新过程如下图所示：

三.初始化

记s的长度为m，p的长度为n。为便于状态更新，减少对边界的判断，初始二维dp数组维度为(m + 1)*（n + 1)，其中第一行和第一列的状态分别表示字符串s和p为空时的情况。

显然dp[0][0] = true。对于其他 $dp[0][j]$ ,当 $p[j] \neq '*'$ 时， $p[0,...,j]$ 无法与空字符匹配，因此有 $dp[0][j] = false$ ;而当 $p[j] = '*'$ 时，则有 $dp[0][j] = dp[0][j-2]$ 。

以p= "c * a *b"为例， $dp[0][*] = [true, false, true, false,true,false]$

需要特别注意的是：由于dp数组维度为(m + 1)*（n + 1)，在具体的代码实现时， $s[i-1]$ 和 $p[j-1]$ 才是分别表示 s 和 p 中的第 i 和第 j 个字符。

代码：

1. 二维DP

动态规划的基础代码如下：


class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector< vector<int> > dp(m+1, vector<int>(n+1));
 
        //初始化
        dp[0][0] = true;
        for(int j = 1; j <= n+1; j++){
            if(p[j-1] == '*'){
                dp[0][j] = dp[0][j-2];
            }
        }
 
        //状态更新
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s[i-1] == p[j-1] || p[j-1] == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j-1] == '*'){
                    if(s[i-1] != p[j-2] && p[j-2] != '.'){
                        dp[i][j] = dp[i][j-2];
                    }
                    else{
                        dp[i][j] = dp[i][j-2] | dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
};

2.一维DP: 动态规划的滚动数组优化

在上面的状态转移方程中，每一行的 $dp[i][j]$ 状态值都只与上一行（正上方）的 $dp[i-1][*]$ 和本行的 $dp[i][*]$ 状态值有关，因此可基于滚动数组的思想对状态空间dp进行优化而省去第一维度。

代码：


class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<int> dp(n+1);
 
        //初始化
        dp[0] = true;
        for(int j = 1; j <= n; j++){
            if(p[j-1] == '*'){
                dp[j] = dp[j-2];
            }
        }
 
        //状态更新
        for(int i = 1; i <= m; i++){
            vector<int> dp2(n+1);
            for(int j = 1; j <= n; j++){
                if(s[i-1] == p[j-1] || p[j-1] == '.'){
                    dp2[j] = dp[j-1];
                }
                else if(p[j-1] == '*'){
                    if(s[i-1] != p[j-2] && p[j-2] != '.'){
                        dp2[j] = dp2[j-2]; 
                    }
                    else{
                        dp2[j] = dp2[j-2] | dp[j];
                    }
                }
            }
            dp = dp2;
        }
        return dp[n];
    }
};

3.一维DP：动态规划的滚动数组优化 + 提前结束

注意到，在状态转移过程中，每一行的 $dp[i][j]$ 的状态值都只与上一行（正上方）的 $dp[i-1][*]$ 和本行的 $dp[i][*]$ 状态值有关，因此上一行的 $dp$ 值均为 false，即对于 s 中的某一个字符无法在 p 中得到匹配时，整个 s 字符串也就无法得到匹配，可直接返回 false 而提前终止程序。


class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<int> dp(n+1);
 
        //初始化
        dp[0] = true;
        for(int j = 1; j <= n; j++){
            if(p[j-1] == '*'){
                dp[j] = dp[j-2];
            }
        }
 
        //状态更新
        for(int i = 1; i <= m; i++){
            vector<int> dp2(n+1);
            int sum = 0;
            for(int j = 1; j <= n; j++){
                if(s[i-1] == p[j-1] || p[j-1] == '.'){
                    dp2[j] = dp[j-1];
                }
                else if(p[j-1] == '*'){
                    if(s[i-1] != p[j-2] && p[j-2] != '.'){
                        dp2[j] = dp2[j-2]; 
                    }
                    else{
                        dp2[j] = dp2[j-2] | dp[j];
                    }
                }
                sum = sum + dp2[j];
            }
            dp = dp2;                       //滚动数组
            if(sum == 0){                  //提前结束
                return false;
            }
        }
        return dp[n];
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50758

刷题：动态规划（DP）之正则表达式匹配_正则表达式匹配 动态规划

刷题：动态规划（DP）之正则表达式匹配_正则表达式匹配动态规划