Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:


	'?' Matches any single character.
	'*' Matches any sequence of characters (including the empty sequence).


The matching should cover the entire input string (not partial).

&nbsp;
Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".


Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation:&nbsp;'*' matches any sequence.


Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation:&nbsp;'?' matches 'c', but the second letter is 'a', which does not match 'b'.


&nbsp;
Constraints:


	0 &lt;= s.length, p.length &lt;= 2000
	s contains only lowercase English letters.
	p contains only lowercase English letters, '?' or '*'.


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m= len(s)
        n= len(p)

        dp = [[False]*(n+1) for i in range(m+1)]

        dp[0][0] = True

        for j in range(len(p)):
            if p[j] == "*":
                dp[0][j+1] = dp[0][j]

        for i in range(1,m+1):
            for j in range(1,n+1):
                if p[j-1] == "*":
                    dp[i][j] = dp[i-1][j] or dp[i][j-1]

                elif s[i-1] == p[j-1] or p[j-1] == "?":
                    dp[i][j] = dp[i-1][j-1]

        return dp[-1][-1]
class Solution {
    public boolean isMatch(String s, String p) {
        int i=0;
        int j=0;
        int starIdx=-1;
        int lastMatch=-1;

        while(i<s.length()){
            if(j<p.length() && (s.charAt(i)==p.charAt(j) ||
              p.charAt(j)=='?')){
                i++;
                j++;
            }else if(j<p.length() && p.charAt(j)=='*'){
                starIdx=j;
                lastMatch=i;
                j++;
            }else if(starIdx!=-1){
            //there is a no match and there was a previous star, we will reset the j to indx after star_index
            //lastMatch will tell from which index we start comparing the string if we encounter * in pattern
                j=starIdx+1;
                lastMatch++; // we are saying we included more characters in * so we incremented the index
                i=lastMatch;

            }else{
                return false;
            }
        }

        while(j<p.length() && p.charAt(j)=='*') j++;

        if(i!=s.length() || j!=p.length()) return false;

        return true;

    }
}
class Solution {
public:
    bool match(int i, int j, string &a, string &b, vector<vector<int>>&dp)
    {
        if(i<0 && j<0) return true;
        if(i>=0 && j<0) return false;
        if(i<0 && j>=0)
        {
            for(;j>-1;j--) if(b[j]!='*') return false;
            return true;
        }
        if(dp[i][j]!=-1) return dp[i][j];
        if(a[i]==b[j] || b[j]=='?') return dp[i][j] = match(i-1,j-1,a,b,dp);
        if(b[j]=='*') return dp[i][j] = (match(i-1,j,a,b,dp) | match(i,j-1,a,b,dp));
        return false;
    }
    bool isMatch(string s, string p) {
        int n=s.size(), m=p.size();
        vector<vector<int>>dp(n+1,vector<int>(m+1,-1));
        return match(n-1,m-1,s,p,dp);
    }
};
var isMatch = function(s, p) {
    const slen = s.length, plen = p.length;
    const dp   = new Map();
    
    const solve = (si = 0, pi = 0) => {
        // both are compared and are equal till end
        if(si == slen && pi == plen) return true;
        // we have consumed are wildcard string and still s is remaining
        if(pi == plen) return false;
        // we still have wildcard characters remaining
        if(si == slen) {
            while(p[pi] == '*') pi++;
            return pi == plen;
        }
           
        const key = [si, pi].join(':');
        if(dp.has(key)) return dp.get(key);
        
        let ans = false;
        if(p[pi] == '*') {
			// drop * or use it
            ans = solve(si, pi + 1) || solve(si + 1, pi);
        } else {
            const match = s[si] == p[pi] || p[pi] == '?';
            if(match) ans = solve(si + 1, pi + 1);   
        }
        
        dp.set(key, ans);
        
        return ans;
    }
    return solve();
};
Wildcard Matching