这是 2020 年 7 月 5 日的力扣每日一题。总共有两种解法,第一种是动态规划,就当复习了。第二种是贪心解法,这是我第一次遇到的解法,特此记录一下。

题目

给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?''*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。

两个字符串 完全匹配 才算匹配成功。

说明

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 ?*

示例 1

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

示例 2

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

示例 3

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

示例 4

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5

输入:
s = "acdcb"
p = "a*c?b"
输出: false

动态规划

动态规划的核心在于构建 dp 函数。对于这种两个字符串的题。一般都是定义一个二元函数:

dp(i, j)字符串 si 个字符与 字符串 pj 个字符是否匹配。

然后开始思考状态转移。

状态转移方程

这里我们根据 字符串 pj 个字符的类型类分类。

  • 如果 p[j] 为普通字母,则很容易想到状态转移方程为:

$$ dp(i, j) = dp(i-1, j-1) ∧ s[i] = p[j] $$

  • 如果 p[j]?,因为 ? 可以匹配任何字母,所以它们不需要当前位字母相同,转移方程为:

$$ dp(i, j) = dp(i-1, j-1) $$

  • 如果 p[j]*,因为 * 可以匹配任何字符串,这里我们先假设 * 表示空字符串,此时转移方程:

$$ dp(i, j) = dp(i, j-1) $$

  • 直接把 * 去掉后可以匹配
  • 然后假设 * 表示 1 个字符,则方程为:

$$ dp(i, j) = dp(i-1, j) $$

  • 然后假设 * 表示 k 个字符,则方程为:

$$ dp(i, j) = dp(i-k, j) $$

  • 以此类推,我们发现 dp(i-k, j) = dp(i-1, j),因为假设 * 表示 k 个字符的时候,我们往前的时候总会遇到 *只剩下一个字符可以表示的时候。所以对于 * 可表示成字符串的情况状态方程直接为:

$$ dp(i, j) = dp(i-1, j) $$

  • 所以,如果 p[j]*,状态转移方程为:

$$ dp(i, j) = dp(i, j-1) ∨ dp(i-1, j) $$

  • * 可以表示为空字符串或 * 可以表示为字符串

至此,我们可以写出总的状态转移方程:

$$ dp(i, j)=\left\{ \begin{aligned} dp(i-1, j-1) & \qquad p[j]='?' \\ dp(i, j-1) ∨ dp(i-1, j) & \qquad p[j] ='*' \\ dp(i-1, j-1) ∧ s[i] = p[j] & \qquad else \end{aligned} \right. $$

边界条件

我们发现状态转移方程中有 i-1j-1 ,而所以边界条件为 dp(0, j) 和 dp(i, 0)
其中:

  • $dp(0,0) = true$,空字符串和空模式字符串肯定是匹配的。
  • $dp(i, 0) = false$,空模式字符串无法匹配除了空字符串以外任何字符串。
  • $dp(0,j)$ 则比较复杂,只有当模式字符串前 j 项都为 *,才有$dp(0,j) = true$,否则 $dp(0,j) = false$

搞定,状态转移方程和边界条件都有了。根据观察,遍历顺序也没有什么特殊要求,直接上代码:

代码

  • 语言:C++
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<int>> dp(s.size()+1 ,vector<int>(p.size()+1, 0));
        dp[0][0] = 1;
        for(int j = 1 ; j < p.size()+1 ; j ++){
            if(p[j-1] == '*'){
                dp[0][j] = 1;
            }else{
                break;
            }
        }
        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] || dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j-1]&&(p[j-1] == '?' || s[i-1] == p[j-1]);
                }

            }
        }
        return dp[s.size()][p.size()]==1;
    }
};

空间优化

因为状态方程里只有 i-1j-1,所以我们可以使用两个一位数组来代替二维数组。具体就不展开了。

贪心

这个贪心解法是我没有想到的,就当开拓思路了。

贪心算法是一种从局部最优解得出整体最优解的思路。即不去考虑整体,直接从局部去求最优解。

思路

以上动态规划的算法主要受限于 * 的匹配,因为 * 可以匹配任何字符串,所以在匹配的时候就有很多种可能。所以我们需要想办法,去掉*号的匹配过程 。

需要明确,多个 * 连接起来效果和一个 * 是一样的。

特殊情况

假设有模式字符串 *abc*,此时我们可以发现,因为 * 可以是任何字符串,所以只要字符串 s中含有 abc 子串,则可以匹配。此时我们去掉了* 的匹配过程,问题直接转换为在字符串 s中寻找 abc 子串。寻找子串的过程可以直接暴力,因为? 的存在,KMP反而难以处理。

那如果有模式字符串 *abc*dfe*fws*fews* 呢?其实根据上面的讲解,思路已经很清晰了。我们可以吧模式字符串分割成 abcdeffwsfews,然后在字符串s 中从左到右依次寻找子串。每次都找到该子串最早出现的位置。一直找到最后一个子串 fews。如果都能找到这说明字符串可以匹配。

例如以下输入:(字符串s 并不包含空格,只是为了方便阅读)

s = adfafdbscsds
p = *a*b*c*s*

首先我们同样将 模式字符串p 按照 * 分割成 abcs
然后我们在 字符串s 中寻找子串 a,第一个就是,剩下 字符串sdfafdbscsds,然后继续寻找 子串 b,剩下为 scsds,然后寻找子串 c,剩下为 sds,然后寻找子串 s,剩下为 ds

至此,最后一个子串都有匹配,所以字符串可以匹配。

一般情况

然而一般情况 模式字符串p 可能首尾并不是 *,其实也很好处理,因为如果首尾不是 *,这说明两个字符串首尾必须一致。

例如以下输入:

s = abcdadfafdbscsdsdddd
p = abcd*a*b*c*s*dddd

问题可以转换为:

s = adfafdbscsds
p = *a*b*c*s*

即把首尾去掉,如果首尾不一致则直接返回无法匹配。

最后注意在寻找子串的时候 ? 的处理,? 可以匹配任何一个字母。

代码

这里代码转载于力扣官方题解

  • 语言:C++
class Solution {
public:
    bool isMatch(string s, string p) {
        auto allStars = [](const string& str, int left, int right) {
            for (int i = left; i < right; ++i) {
                if (str[i] != '*') {
                    return false;
                }
            }
            return true;
        };
        auto charMatch = [](char u, char v) {
            return u == v || v == '?';
        };

        while (s.size() && p.size() && p.back() != '*') {
            if (charMatch(s.back(), p.back())) {
                s.pop_back();
                p.pop_back();
            }
            else {
                return false;
            }
        }
        if (p.empty()) {
            return s.empty();
        }

        int sIndex = 0, pIndex = 0;
        int sRecord = -1, pRecord = -1;
        while (sIndex < s.size() && pIndex < p.size()) {
            if (p[pIndex] == '*') {
                ++pIndex;
                sRecord = sIndex;
                pRecord = pIndex;
            }
            else if (charMatch(s[sIndex], p[pIndex])) {
                ++sIndex;
                ++pIndex;
            }
            else if (sRecord != -1 && sRecord + 1 < s.size()) {
                ++sRecord;
                sIndex = sRecord;
                pIndex = pRecord;
            }
            else {
                return false;
            }
        }
        return allStars(p, pIndex, p.size());
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/wildcard-matching/solution/tong-pei-fu-pi-pei-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。