动态规划-两个数组的dp问题——44.通配符匹配

1.题目解析

题目来源：44.通配符匹配——力扣

测试用例

2.算法原理

1.状态表示

本题属于两个数组的dp问题，这里需要使用p中的字符消去s中的字符且p中有特殊字符可以匹配s中的普通字符，属于寻找相同子序列的变式，所以需要一个二维dp表且表达意义为:

dp[i][j]:p的[0,j]区间是否可以匹配s的[0,i]区间的所有字符，所以数据类型为布尔类型

2.状态转移方程

由于p中的字符可以分为三类，所以如下图对状态转移方程的分析

3.初始化

初始化需要设置虚拟位置并给初值，具体如下图

4.填表顺序

从上到下，每一行从左到右

5.返回值

根据状态表示可知需要返回dp[m][n]

3.实战代码

代码解析

class Solution {
public:bool isMatch(string s, string p) {int m = s.size();int n = p.size();vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));dp[0][0] = true;s = " " + s;p = " " + p;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 (p[j] == '*') {dp[i][j] = dp[i - 1][j] || dp[i][j - 1];} else {dp[i][j] =(p[j] == '?' || s[i] == p[j]) && dp[i - 1][j - 1];}}}return dp[m][n];}
};