Wildcard Matching.cpp

//Programmed in C++ | Author: Anshuman Pratik
//For * take 2 cases, one when it is Empty string followed by reducing pattern pointer by 1, and other when replaced by *char i.e. for b in String, we can replace with *b so that pointer in pattern remains at * after cancelling out from String
class Solution {
public:
    bool solve(string& str, string& pattern, int i, int j, vector<vector<int> >& dp) {
        //base case
        if(i<0 && j<0)
            return true;
        
        if(i>=0 && j<0)
            return false;
        
        if(i<0 && j>=0) {
            for(int k=0; k<=j; k++) {
                if(pattern[k] != '*') {
                    return false;
                }
            }
            return true;
        }
        
        if(dp[i][j] != -1)
            return dp[i][j];
        
        //Matching of String and Pattern
        if(str[i] == pattern[j] || pattern[j] == '?')
            return dp[i][j] = solve(str, pattern, i-1, j-1, dp);
        else if(pattern[j] == '*')
            return dp[i][j] = ( solve(str, pattern, i-1, j, dp) || solve(str, pattern, i, j-1, dp) );
        else
            return false;
        
    }
    bool isMatch(string s, string p) {
        vector<vector<int> > dp(s.length(), vector<int>(p.length(), -1));
        return solve(s, p, s.length()-1, p.length()-1, dp);
    }
};