leetcode 44. 通配符匹配(困难，dp)

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。

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

说明:

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’。

🧡 算法分析

此题方法是用dp

和leetcode 第10题 相似

1. 设状态 f(i,j) 表示字符串 s 的前 i 个字符和字符串 p 的前 j 个字符能否匹配。这里假设 s 和 p 的下标均从 1 开始。初始时，f(0,0)=true。
2. 当p[j] != '*'时，f[i - 1][j - 1] && (s[i] == p[j] || p[j] == ‘?’);
3. 当 p(j) == '’ 时，这时 可以代表0个字符， 1个字符 …, 这时的状态转移方程为 f(i, j) = f(i, j - 1) || f(i-1, j -1) || f(i - 2, j - 1) || ... || f(0, j - 1)。此时在写一个f(i - 1, j)的方程 f(i - 1, j) = f(i - 1, j - 1) || f(i-2, j -1) || f(i - 3, j - 1) || ... || f(0, j - 1)，你会发现, 后面的部分都是一一对应的，整合这两个方程得到：f(i, j) = f（i, j -1) || f(i - 1, j)
4. 初始状态 f(0,0)=true；循环枚举 i 从 0 到 n；j 从 1 到 m。因为 f(0,j)有可能是有意义的，需要被转移更新。
5. 最终答案为 f(n,m)。

【注】： 第10题转移方程为： f(i, j) = f（i, j -2) || f（i - 1, j）&& s[i] == p[j]
本题转移方程为： f(i, j) = f（i, j -1) || f(i - 1, j)
所以在代码实现的时候后面是没有&& 条件的

💚 代码实现

class Solution {
public:
    bool isMatch(string s, string p) {
        // 动态规划

        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;   // 从字符串1开始

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
        f[0][0] = true;
        for(int i = 0; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                //if(j + 1 <= m && p[j + 1]== '*') continue;
                if(i && p[j] != '*')
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');
                else if (p[j] == '*')
                    f[i][j] = f[i][j - 1] || i && f[i - 1][j];
            }

        return f[n][m];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

执行结果：

💙 时间复杂度分析

状态数为 O(nm)，每次转移仅需常数时间，故总时间复杂度为 O(nm)。

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！