动态规划解决正则匹配问题

题目描述

Problem: LCR 137. 模糊搜索验证
设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：

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

请返回用户输入内容 input 所有字符是否可以匹配原文字符串 article。

思路

这题是一个正则匹配题，可以用动态规划来解决。具体来说，$dp[i][j]$表示$s$的前$i-1$项和$p$的前$j-1$项是否可以匹配，我们要通过$dp[a][b](a\leq i, b\leq j)来计算得出它$。注意这里假设字符串的第0位为空，因此$dp[0][0]$一定为true，它代表了两个空字符串是可以匹配的。

解题过程

初始化

我们可以考虑初始化第一行还是初始化第一列。
对第一列来说，除了$dp[0][0]$为true之外其他的一定都是false,因为一个非空的真实字符串不可能匹配一个空的模糊字符串；但是第一行不一样，一个非空的模糊字符串是可能匹配一个空的字符串的，例如“空”和“a*”就是匹配的。于是我们选择初始化第一列：

int n = s.size(); int m = p.size();
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false)); // 初始化dp全都为false
dp[0][0] = true; //空序列对空序列，可以匹配

由于我们初始化的是第一列，因此我们计算动态规划的顺序应该为先对列遍历，再对行遍历：

for(int j = 1; j <= m; j++)  // 计算dp[i][j]的值
        {
            for(int i = 0;i <= n; i++){}
            ...
        }

转移方程

我们可以根据 $p[j-1]$ 的值来进行分类讨论：

$p[j-1]$=“*”

这个情况比较复杂，需要考虑三种情况：

1. *前面的字母出现0次是否匹配：

   bool a = (j >= 2) && dp[i][j - 2]; // 0个*前的字母是否使其成立

2. *前面的字母出现一次或者一次以上是否匹配：

   bool b = (i >= 1) && (j >= 2) && dp[i - 1][j] && (p[j - 2] == s[i - 1]);

3. *前面的字母是"."时，只需要考虑：

   bool c = (i >= 1) && dp[i - 1][j];

只要 a, b, c 中有一个为 true，那么 $dp[i][j]$ 就为 true。

$p[j-1]$=“.”

只要前一个序列相互配对即可：

dp[i][j] = (i >= 1) && dp[i - 1][j - 1];

$p[j-1]$=字母

这样更简单，只要当前字母匹配且前一个序列可以相互匹配就行。

dp[i][j] = (i >= 1) && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1]);

不难发现2.1的b，c两种情况可以结合，结合之后就得到了正确完整的的代码。

复杂度

• 时间复杂度: $O(mn)$
• 空间复杂度: $O(mn)$
• 这题应该可以用状态压缩把空间优化到$O(\max(m,n))$的，但我没去写，什么时候把它补上。

Code

class Solution {
public:
    bool articleMatch(string s, string p) {
        int n = s.size(); int m = p.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false)); // 初始化dp全都为false
        dp[0][0] = true; //空序列对空序列，可以匹配

        for(int j = 1; j <= m; j++)  // 计算dp[i][j]的值
        {
            for(int i = 0;i <= n; i++)
            {
                if(p[j - 1] == '*')
                {
                    bool a = (j >= 2) && dp[i][j - 2]; // 0个*前的字母是否使其成立
                    bool b = (i >= 1) && (j >= 2) && dp[i - 1][j] && ((p[j - 2] == s[i - 1]) || p[j - 2] == '.');  
                    //  >=1个*前的字母是否使其成立，或者是特殊情况p[j - 2] = '.'
                    dp[i][j] = a || b;            
                }
                else if(p[j - 1] == '.') dp[i][j] = (i >= 1) && dp[i - 1][j - 1]; // 是'.'
                else dp[i][j] = (i >= 1) && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1]); // 是字母
            }
        }

        return dp[n][m];
    }
};