Leetcode 44. 通配符匹配 | Crystal’s Blog

type

Post

status

Published

date

Jan 4, 2024

slug

leetcode-44

summary

数据结构与算法，动态规划

🤔 循迹——暴力之冗余

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

'?' 可以匹配任何单个字符。

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

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

示例 1：


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

可以看出，主要是'*'的匹配需要思考。可以用dfs暴力对每一个'*'枚举匹配's'中的每一串字符。比如考虑两个字符串s='abcde'和p='**f' ，其中两个'*' 的匹配如下图所示。需要遍历5个字符串才能输出false 。但是当遍历到最后一个字符'f' 时只需要知道上一个字符'*' 能否被匹配和匹配到's' 哪个位置即可，有多少种匹配方式不用管。5个字符串的'd' 都是匹配'*' ,但是只用算一种即可。这是暴力的冗余之处。

📝优化——一维DP

那么怎么记录p中每个字符是否能被匹配，以及能被s中哪个字符匹配。这两个信息可以用二维数组表示：

dp[i][j] :p 中第i个字符与s 中第j个字符是否能匹配，值为0表示不能，值为1表示可以。

转移方程如下图所示：

由于第i轮的值只和上一轮相关，所以略去第一维，倒序遍历第二维。但是当p[i]是星号时。不从dp[i][j-1]转换过来，而是只要前i个字符有一个能匹配成功即可，用t数组记录。


class Solution {
public:
    bool isMatch(string s, string p) {
        int n1 = s.size(), n2 = p.size();
        vector<int> dp(n1 + 1); // dp[j]代表p中第i个字符匹配s中第j个字符
        vector<int> t(n1 + 1);
        dp[0] = 1;
        for (int i = 0; i < n2; i++) {
            t[0] = dp[0];
            for (int j = 1; j <= n1; j++) {
                t[j] = t[j - 1] | dp[j];
            }
            for (int j = n1; j > 0; j--) {

                if (p[i] == s[j - 1] || p[i] == '?') {
                    dp[j] = 0;
                    if (dp[j - 1]) {
                        dp[j] = 1;
                    }
                } else {
                    if (p[i] == '*') {
                        if (dp[j] || t[j - 1]) {
                            dp[j] = 1;
                        }
                    } else {
                        dp[j] = 0;
                    }
                }
            }
            if (p[i] == '*' && dp[0]) {
                dp[0] = 1;
            } else {
                dp[0] = 0;
            }
        }
        if (dp[n1]) {
            return true;
        }
        return false;
    }
};

🤗总结

时间复杂度为 O(mn)。空间复杂度为 O(n)。

空间复杂度相比二维DP降了，但是边界处理不优雅。