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".
Example 5:
Input: s = "acdcb", p = "a*c?b"
Output: false
Solution: (DP)
class Solution
{
public:
bool isMatch(string s, string pattern)
{
//Removing extra stars
string p = "";
bool isFirst = true;
for (int i = 0; i < pattern.length(); i++)
{
if (pattern[i] == '*')
{
if (isFirst)
{
p = p + pattern[i];
isFirst = false;
}
}
else
{
p = p + pattern[i];
isFirst = true;
}
}
int n = s.length();
int m = p.length();
vector<vector<bool>> v(n + 1, vector<bool>(m + 1, false));
v[0][0] = true;
if (p[0] == '*')
{
v[0][1] = true;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
//case1: if(equal or ?)
if (s[i - 1] == p[j - 1] || p[j - 1] == '?')
{
v[i][j] = v[i - 1][j - 1];
}
//case2: if(*)
else if (p[j - 1] == '*')
{
v[i][j] = v[i - 1][j] || v[i][j - 1];
}
//not match
else
{
v[i][j] = false;
}
}
}
return v[n][m];
}
};