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).
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: '*' matches any sequence.
Example 3:
Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
https://www.youtube.com/watch?v=3ZDZ-N0EPV0&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&index=25&ab_channel=TusharRoy-CodingMadeSimple
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();
vector<vector<bool>> dp(m+1,vector<bool>(n+1));
dp[0][0] = true;
for(int j=1;j<=n;j++)
{
if(p[j-1]=='*')
dp[0][j] = dp[0][j-1];
else
dp[0][j] = false;
}
for(int i=1;i<=m;i++)
dp[i][0] = false;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(s[i-1]==p[j-1]||p[j-1]=='?')
dp[i][j] = dp[i-1][j-1];
else if(p[j-1]=='*')
dp[i][j] = dp[i-1][j] || dp[i][j-1];
else
dp[i][j] = false;
}
}
return dp[m][n];
}
};
// Time Complexity : O(n^2)
// Space Complexity : O(n^2)