DP——正则表达式匹配

Leetcode hard题

Rating:[5, 5, 4]
本题主要工作围绕"c*"应该匹配那些元素展开。难点是选择dp、写出递推方程并正确填表。

解法：dp

1.输入输出

(1) 输入：
字符串s，长度为n。
正则表达式p，长度为m。正则表达式中含有单个字符（记为'c'），"c*"或 '.' 。c是小写字母。正则表达式合法并遵循通用规则。

(2) 输出：正则是否匹配字符串(T/F)

2.递推方程

设 dp[i, j] 表示s[0, i-1]（前i个字符）是否被p[0, j-1]匹配。注意由于存在空串和空正则匹配的情况，所以dp[0, j]表示s首前元素（空字符）是否能被p的前j个字符匹配。设judge[i, j]表示s[i]否被p[j]一对一匹配。匹配的情况包括两字符相等或者p[j] = '.'。
dp[i, j] = dp[i, j-1]，if p[j-1] = ' * ' (1)
judge[i-1, j-1] AND dp[i-1, j-1]，if p[j-1] != ' * ' AND p[j+1-1] != ' * ' (2)
dp[i, j-1] OR (judge[i-1, j-1] AND dp[i-1, j])，if p[j+1-1] = ' * ' (3)

分析：
(1) 对于p中的"c*"，这两个字符作为整体来看待，对于' * ' 直接抄写'c'的dp值
(2) 对于普通字符或单独的'.'，当前位置上的元素且s当前位置前的所有字符能被p当前位置前的匹配。
(3) 遇到"c*"模式中的'c'，我们可以让"c*"匹配0个元素，此时要保证s[0, i-1]被p当前元素之前的模式匹配。（当然也可以被结尾在j之后的模式匹配，但是这种情况在递推中会被包含到）。或者我们可以让"c*"匹配当前元素，这时候"c*"可以匹配或不匹配前面一个元素。省略不匹配前面元素的情况是因为已被包含在子问题dp[i-1, j]中，是子问题对应情况(3)在OR前面的部分。

边界情况：
(1) dp[0, 0] = true;
(2) dp[k, 0] = false (0 < k <= n); 非空子串不能被空正则匹配
(3) dp[0, k] (0 < k <= m) 空子串可能能被非空正则匹配，需要判断。此时正则只能包含若干个"c*"。

3.时空复杂度

时间: O(nm)
空间：O(nm)

参考代码：

class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1, false));
        //1. 为了减少主体部分判断单独处理边界情况
        dp[0][0] = true; //边界1
        for(int i = 1; i < s.size()+1; ++i){ //边界2，模式为空的情况
            dp[i][0] = false;
        }
        for(int j = 1; j < p.size()+1; j+=2){ //边界3，串为空情况，j为序号，注意转换成下标
            if(j+1 < p.size()+1 && p[j+1-1] == '*')
                dp[0][j] = dp[0][j+1] = dp[0][j-1];
            else
                break;
        }
        //2. 主体
        for(int i = 1; i < s.size()+1; ++i){
            for(int j = 1; j < p.size()+1; ++j){
                if(p[j-1] == '*') dp[i][j] = dp[i][j-1]; //情况1
                else if(j+1 == p.size()+1 || p[j+1-1] != '*') //情况2
                    dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == '.') && dp[i-1][j-1]; 
                else //情况3
                    dp[i][j] = ((s[i-1] == p[j-1] || p[j-1] == '.') && dp[i-1][j]) || 
                    dp[i][j-1]; 
            }
        }
        return dp.back().back();
    }
};