leecode 44. 通配符匹配

leecode 44. 通配符匹配

题目描述

给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

思路

step1：开辟一个二维数组，标志是不是一样
std::vector<std::vector>dp(m+1,vector(n+1)); m表示输入字符串s的大小，n表示的是字符模式字符串的大小。
step2：遍历 字符模式p的串，如果其是 * 的话，则肯定是true

for(int i = 1; i <=n ; ++i) {
           if(p[i-1] != '*') {
                break;
           }
           dp[0][i] = true;
} 

step3:
3.1 若当前模式串是* 的话，则需要看前一个或者 上斜一个的状态。因为上斜一个表示前一个的匹配状态。 前一个是为兼容 ✳，因为它可以匹配多个。
3.2 若当前不是*的话，若当前是？ 号的话，或者于对应位置的s串相同的话，则它的状态= 上斜一个(前一个)的状态 。
3.3 终点即是最后是不是一样的结果，也就是dp[m][n];

代码

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