44. Wildcard Matching
Đề Bài
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 <= 2000scontains only lowercase English letters.pcontains only lowercase English letters,'?'or'*'.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n×m)
💾 Không gian
O(n×m)
Lời Giải
C++
0044-wildcard-matching.cpp
class Solution {
private:
string s, p;
int n, m;
public:
vector<vector<int>> memo;
int dp(int i, int j) {
if (memo[i][j] != -1) {
return memo[i][j];
}
if (j == m) {
return memo[i][j] = i == n;
}
if (i == n) {
return memo[i][j] = p[j] == '*' and dp(i, j + 1);
}
if (p[j] == '?' or s[i] == p[j]) {
return memo[i][j] = dp(i + 1, j + 1);
}
if (p[j] == '*') {
return memo[i][j] = dp(i + 1, j) or dp(i, j + 1);
}
return memo[i][j] = 0;
}
bool isMatch(string s, string p) {
n = s.size(), m = p.size();
memo.resize(n + 1, vector<int>(m + 1, -1));
this->s = s;
this->p = p;
return dp(0, 0);
}
};