44. 通配符匹配（动态规划）

Problem: 44. 通配符匹配

文章目录

• 题目
• 思路
• Code
• DFS（超时）

题目

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

示例 1：

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

思路

两个思路 ，一种就是搜索dfs(代码超时，附上有心人优化)。另一种就是动态规划。

假设 dp[i][j] 表示字符串s的前i字符和匹配串p的前j个字符的匹配结果。
分下面情况 ：

1. 当 s[i] 和 p[j] 都是小写字母或者 p[j]是’?‘，如果p[j]=’?’是匹配的，如果s[i] = s[j] 也是匹配的。所以 这两种情况和dp[i-1][j-1]一样。
   
2. 当p[j]是‘*’ ：
   (1) 匹配0个字符 : 相当于把p[j]去掉
   (2) 匹配多个字符 ： 这个比较难理解 ，答案是 $ dp[i][j] = dp[i][j-1] $
   • 使用*。如 s = ‘abc’，p = ‘ab*’，或者 s = ‘abcd’, s = “abcde…”，*号能匹配0个或者多个任意字符。
   • 对应的情况是’abcde’匹配’ab*‘，退一步’abcd’也能匹配’ab*’，‘abc’仍然能匹配’ab*’，‘ab’也能匹配’ab*’，’a’就不能匹配’ab*’了。
   • 即 dp[i-1][j] = dp[i-2][j] | dp[i-3][j] … dp[0][j] 一直找下去, 由于i 是递增遍历的，每次答案都迭代进去了,所以省略了。

Code

class Solution {
public:
    bool isMatch(string s, string p) {
        // 动态规划 
        // dp[i][j] 表示s 的前i 个字符是否匹配p的前j 个字符
        int m = s.size() ; 
        int n = p.size() ;

        // 1. 当 s[i] 和 p[j] 都是小写字母
        // 当 s[i] ==p[j] 时，dp[i][j] = dp[i-1][j-1]
        // 当 s[i] !=p[j] 时 dp[i][j] = false ;
        // 2。 当 p[j]是? 
        // dp[i][j] = dp[i-1][j-1] ; 

        // 3. 当p[j] 是 *
        // (1) 当成空字符串  dp[i][j] = dp[i][j-1] 
        // (2) 使用星星      dp[i][j] = dp[i-1][j]


        // 初始化 
        // dp[0][0] = True ; 
        // dp[i][] = false ; 
        // 特殊 
        vector<vector<int>> dp(m+1, vector<int>(n+1 )) ; 
        dp[0][0] = true ; // 空串一定匹配

        for(int i = 1 ; i <=n ; i++ ) {
            if(p[i-1] =='*') { // s: "" ,p: "*"
                dp[0][i] = true ; 
            }else {
                break ; 
            }
        }
        for(int i = 1 ; i<= m ; i++) {
            for(int j = 1 ; j <=n  ; j++ ) {
                if(p[j-1] == '?'|| s[i-1] == p[j-1] ) { // 匹配 
                    dp[i][j] = dp[i-1][j-1] ; 
                }else if(p[j-1] == '*'){
                    // dp[i][j-1]是匹配空字符
                    // dp[i-1][j] 是匹配多个字符 
                    dp[i][j] = dp[i-1][j] | dp[i][j-1] ;


                }

            }
        }
        return dp[m][n] ; 
    }
};

DFS（超时）

class Solution {
public: 
    bool ans = false ; 
    set<pair<int,int>> memo;  

    void dfs(string s ,string p ,int pos1 ,int pos2 ) {
        if(ans ) return ; 
        if(memo.count({pos1,pos2}) !=0) {
            return ;
        }
        memo.insert({pos1,pos2})  ;
        if(pos1 == s.size() && pos2 == p.size()) {
            ans = true ; 
            return ; 
        }
        while(pos1<s.size() && pos2<p.size() && (s[pos1] == p[pos2] || p[pos2]=='?') ){
            pos1++ ; 
            pos2++ ;
        }
        if(pos1 == s.size() && pos2== p.size()) {
            ans = true ; 
            return ; 
        }else if(p[pos2] =='*') {
            // 粗去连续的* 
            while(pos2 <p.size() -1&& p[pos2+1] =='*') {
                pos2++ ; 
            }
            int cnt = 0 ; 
            while(pos1 + cnt <=s.size()) {
                dfs(s,p,pos1+cnt++ , pos2+1) ;
            }
        }



    }
    bool isMatch(string s, string p) {

        dfs(s,p,0,0) ;

        return ans ; 

    }
};