Wildcard Pattern Matching

Given two strings ‘str’ and a wildcard pattern ‘pattern’ of length N and M respectively, You have to print ‘1’ if the wildcard pattern is matched with str else print ‘0’ .

The wildcard pattern can include the characters ? and *

• ? – matches any single character
• * – Matches any sequence of characters (including the empty sequence)

Note: The matching should cover the entire str (not partial str).

• Time : O(nm)
• Space : O(nm)

c++

class Solution {
    int dp[202][202];
    int helper(string& s, string& p, int i = 0, int j = 0) {
        if(i == s.length() and j == p.length()) return true;
        if(j == p.length()) return false;
        if(i == s.length()) {
            for(int pos = j; pos < p.length(); pos++)
                if(p[pos] != '*') return false;
            return true;
        }
        if(dp[i][j] != -1) return dp[i][j];
        
        dp[i][j] = 0;
        if(p[j] == '?') return dp[i][j] = helper(s, p, i + 1, j + 1);
        if(s[i] == p[j]) return dp[i][j] = helper(s, p, i + 1, j + 1);
        if(p[j] == '*') {
            for(int pos = i; pos <= s.length(); pos++) {
                if(helper(s, p, pos, j + 1))
                    return dp[i][j] = true;
            }
        }
        return dp[i][j];
    }
public:
/*You are required to complete this method*/
    int wildCard(string pattern, string str) {
        memset(dp, -1, sizeof dp);
        string newPattern = "";
        for(auto& ch : pattern) {
            if(ch == '*') {
                if(newPattern.empty() or newPattern.back() != '*') newPattern.push_back(ch);
            } else newPattern.push_back(ch);
        }
        return helper(str, newPattern);
    }
};