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".
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
if (n > 30000) return false;
vector<bool> cur(m + 1, false);
cur[0] = true;
for (int j = 1; j <= n; j++) {
bool pre = cur[0];
cur[0] = cur[0] && p[j - 1] == '*';
for (int i = 1; i <= m; i++) {
bool temp = cur[i];
if (p[j - 1] != '*')
cur[i] = pre && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
else cur[i] = cur[i - 1] || cur[i];
pre = temp;
}
}
return cur[m];
}
};
