每日OJ题_两个数组dp④_力扣44. 通配符匹配

力扣44. 通配符匹配

解析代码

力扣44. 通配符匹配

44. 通配符匹配

难度困难

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

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

示例 2：

输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。

示例 3：

输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

提示：

0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、'?' 或 '*' 组成

class Solution {
public:
    bool isMatch(string s, string p) {

    }
};

解析代码

状态表示：

对于两个字符串之间的 dp 问题，我们一般的思考方式如下：

选取第⼀个字符串的 [0, i] 区间以及第⼆个字符串的 [0, j] 区间当成研究对象，结合题目的要求来定义状态表示。然后根据两个区间上最后一个位置的字符，来进行分类讨论，从而确定状态转移方程。

dp[i][j] 表示： p 字符串 [0, j] 区间内的子串能否匹配字符串 s 的 [0, i] 区间内的子串。

状态转移方程：

根据最后一个位置的元素，结合题目要求，分情况讨论：

当 s[i] == p[j] 或 p[j] == '?的时候，此时两个字符串匹配上了当前的一个字符，只能从 dp[i - 1][j - 1] 中看当前字符前面的两个子串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i - 1[j - 1] ；
当 p[j] == '*' 的时候，此时匹配策略有两种选择：

一种选择是： * 匹配空字符串，直接继承状态 dp[i][j - 1] ，此时 dp[i][j] = dp[i][j - 1] ；
另一种选择是： * 向前匹配 1 ~ n 个字符，直至匹配上整个 s 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；

当 p[j] 不是特殊字符，且不与 s[i] 相等时，无法匹配，p[i][j] = flase。

三种情况加起来，就是所有可能的匹配结果。综上所述，状态转移方程为：

当 s[i] == p[j] 或 p[j] == '?' 时： dp[i][j] = dp[i][j - 1] ;
当 p[j] == '*' 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ;

这个状态转移方程时间复杂度为O（N^3），要想想优化。

优化：当发现计算一个状态的时候，需要一个循环才能搞定的时候，我们要想到去优化。优化的方向就是用一个或者两个状态来表示这一堆的状态。通常就是把它写下来，然后用数学的方式做一下等价替换：

当 p[j] == '*' 时，状态转移方程为：dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1]......

发现 i 是有规律的减小的，因此我们去看看 dp[i - 1][j] ，列出 dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1] ......

然后就能发现， dp[i][j] 的状态转移方程里面除了第一项以外，其余的都可以用dp[i -1][j] 替代。因此优化我们的状态转移方程为： dp[i][j] = dp[i][j - 1] || dp[i - 1][j]。

初始化、填表顺序、返回值：

初始化：空串是有研究意义的，因此我们将原始 dp 表的规模多加上一行和一列，表示空串。由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。由于需要用到前一行和前一列的状态，初始化第一行、第一列即可。

dp[0][0] 表示两个空串能否匹配，答案是显然的，初始化为 true 。

第一行表示 s 是一个空串， p 串和空串只有一种匹配可能，即 p 串表示为 "***" ，此时也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "*" 的 p 子串和空串的 dp 值设为 true 。

第一列表示 p 是一个空串，不可能匹配上 s 串，跟随数组初始化成false即可。

填表顺序：从上往下填写每一行，每一行从左往右，最后返回dp[m][n]。

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        s = " " + s, p = " " + p;
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        // dp[i][j] 表示： p字符串[0, j]区间内的子串能否匹配字符串s的[0, i]区间内的子串
        dp[0][0] = true;
        for(int j = 1; j <= n; ++j)
        {
            if(p[j] == '*')
                dp[0][j] = true;
            else
                break;
        }

        for(int i = 1; i <= m; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(s[i] == p[j] || p[j] == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j] == '*')
                    dp[i][j] = (dp[i][j - 1] || dp[i - 1][j]);
            }
        }
        return dp[m][n];
    }
};