30 Days of Code [Day 6]

19 Aug 2021

QUESTION : 44. Wildcard Matching

#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define fv(V) for( auto &it : V )
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size();
        int m = p.size();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
        dp[0][0] = true;
        
        fo(i,1,m+1){
            if(p[i-1] == '*'){
                dp[i][0] = dp[i-1][0];
            }
            fo(j,1,n+1){
                if(p[i-1] == s[j-1] || p[i-1] == '?'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p[i-1] == '*'){
                    dp[i][j] = dp[i-1][j-1] || dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
};