44. Wildcard Matching
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).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
bool dp[2001][2001] {false,};
public:
bool isMatch(string s, string p) {
for(int i = 0; i < p.length() and p[i] == '*'; i++) dp[0][i + 1] = true;
dp[0][0] = true;
for(int i = 1; i <= s.length(); i++) {
bool tmp = false;
for (int j = 1; j <= p.length(); j++) {
if (p[j - 1] == '*') tmp |= dp[i][j] = dp[i - 1][j] | dp[i][j - 1];
else tmp |= dp[i][j] = (s[i - 1] == p[j - 1] or p[j - 1] == '?' ? dp[i - 1][j - 1] : false);
}
if(!tmp) return tmp;
}
return dp[s.length()][p.length()];
}
};
|
