LC 10、正则表达式匹配

superJade / 2023-08-01 / 原文

LC 10、正则表达式匹配

题目描述

LeetCode上的 10、正则表达式匹配，难度困难

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

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

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例：

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

0 <= s.length <=20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

动态规划

让我们来梳理一下状态转移方程，对于字符串 p 来说，有三种字符：

普通字符：需要和 s 中同一位置的字符完全匹配
'.'：能够匹配 s 中同一位置的任意字符
'*'：不能够单独使用 '*'，必须和前一个字符同时搭配使用，数据保证了 '*' 能够找到前面一个字符，能够匹配 s 中同一个位置字符任意次。

所以本题的关键是分析当出现 a*这种字符时，是匹配0个a、还是1个a，两个 a ....

接下来开始定义状态，以及状态转移方程。

状态定义：f(i, j)代表考虑 s中以 i 结尾的子串和 p中的j为结尾的子串是否匹配，即最终我们要求的结果是dp[m][n]。
状态转移：也就是我们要考虑f(i, j)如何求得，前面说到了p有三种字符，所以这里的状态转移也要分为三种情况讨论：

p[j]为普通字符：匹配条件为前面的字符匹配，同时s中的第i个字符和p中的第j位相同。即f(i, j) = f(i - 1, j - 1) && s[i] == s[j] 。
p[j] 为'.'：匹配条件是前面的字符匹配，s中的第 i个字符可以是任意字符，即f(i, j) = f(i - 1, j - 1) && p[j] == '.'。
p[j]为 '*'：读的p[j - 1] 的字符，例如字符a。a可能有很多个。

3.1. 当匹配为 0 个：f(i,j) = f(i, j - 2)

3.2. 当匹配为 1 个：f(i,j) = f(i - 1, j - 2) && (s[i] == p[j - 1] || p[j - 1] == '.')

3.3. 当匹配为 2 个：f(i,j) = f(i - 2, j - 2) && ((s[i] == p[j - 1] && s[i - 1] == p[j - 1]) || p[j] == '.')

我们直到，通过【枚举】来确定 '*' 到底匹配多少个 a 这样的做法，算法复杂度是很高的，我们可以通过适当简化

我们通过上述3系展开式可以直到

将表达式展开有

f(i, j) = f(i, j - 2) || f(i - 1, j - 2) && s[i] 匹配 p[j - 1] || (f(i - 2, j - 2) && s[i - 1 : i] 匹配 p[j - 1])...

上述式子，是从匹配0个以及匹配1个式子得到的。

我们将 i = i - 1代入表达式可得;

f(i - 1, j) = f(i - 1, j - 2) || f(i - 2, j - 2) && s[i - 1] 匹配 p[j - 1] || (f(i - 3, j - 2) && s[i - 2 : i - 1] 匹配 p[j - 1])...

每一个item都差了一个 s[i] 匹配 p[j - 1] 也就是整体相差了一个 s[i] 匹配 p[j - 1] ，所以有

f(i, j) = f(i, j - 2) || (f(i - 1, j) && s[i] 匹配 p[j - 1])

f(i, j) = f(i, j - 2) || (f(i - 1, j) && s[i] == p[j - 1] || p[j - 1] == '.')

代码如下：

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        //这里有一个小技巧，我们可以向s, p头部添加一个“ ”，这样dp[0][0] = true;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
        s = " " + s;
        p = " " + p;
        dp[0][0] = true;
        for(int i = 0; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果是普通字符或者 . 我们可以直接进行状态转移
                if(i - 1 >= 0 && p[j] != '*'){
                    dp[i][j] = dp[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                }
                else if(p[j] == '*'){
                    dp[i][j] = (j - 2 >= 0 && dp[i][j - 2]) ||(i - 1 >= 0 && dp[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'));
                }
                
            }
        } 
        return dp[m][n];
    }
};