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'.
Constraints:
0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.
Intuition
For matching a character and ?
We can match directly, reduce both by 1
But for * we match multiple using for loop
Links
Video Links
Approach 1:
Memoization
C++
class Solution {
public:
bool find_ans(string &s, string &t, int i, int j, vector<vector<int>> &dp){
//Entire string matched
if(i<0 and j<0)
return true;
if(i<0 and j>=0){
/*
This entire block is added to take care of this type of testcase
when first string gets exhausted and second has leading *
abba
*****abba
To match all the leading * with empty
*/
int flag = 1;
for(int start=j; start>=0; start--)
if(t[start] != '*')
flag=0;
if(flag)
return true;
return false;
}
if(i>=0 and j<0)
return false;
if(dp[i][j] != -1)
return dp[i][j];
// Match single string
if(s[i] == t[j] or t[j] == '?'){
if( find_ans(s, t, i-1, j-1, dp) )
return dp[i][j] = true;
}
// Match ith to 0 index for a single *
else if(t[j] == '*'){
for(int start=0; start<=i+1; start++) {
if( find_ans(s, t, i-start, j-1, dp) )
return dp[i][j] = true;
}
}
return dp[i][j] = false;
}
bool isMatch(string s, string t) {
int m = s.size();
int n = t.size();
vector<vector<int>> dp (m, vector<int> (n,-1));
return find_ans(s, t, m-1, n-1, dp);
}
};
```