44. Wildcard Matching
1. Description
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).
2. Example
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’.
3. Constraints
- 0 <= s.length, p.length <= 2000
- s contains only lowercase English letters.
- p contains only lowercase English letters, ‘?’ or ‘*’.
4. Solutions
Recursion(Time Limit Exceeded)
class Solution {
private:
bool isMatch(const string &str, int str_index, const string &pattern, int pattern_index) {
if (str_index == str.size()) {
if (pattern_index == pattern.size() ||
pattern.substr(pattern_index) == string(pattern.size() - pattern_index, '*')) {
return true;
}
return false;
} else {
if (pattern_index == pattern.size()) {
return false;
}
if (pattern[pattern_index] == str[str_index] || pattern[pattern_index] == '?') {
return isMatch(str, str_index + 1, pattern, pattern_index + 1);
} else if (pattern[pattern_index] == '*') {
while (pattern[pattern_index + 1] == '*') {
++pattern_index;
}
return isMatch(str, str_index, pattern, pattern_index + 1) ||
isMatch(str, str_index + 1, pattern, pattern_index + 1) ||
isMatch(str, str_index + 1, pattern, pattern_index);
} else {
return false;
}
}
}
public:
bool isMatch(const string &str, const string &pattern) {
return isMatch(str, 0, pattern, 0);
}
};
Dynamic Programming
n = str.size(), n = pattern.size()
Time complexity: O(mn)
Space complexity: O(mn)
class Solution {
public:
bool isMatch(const string &str, const string &pattern) {
// we don't need the whole matrix, since we only need last two rows
// we could use rotate array to save memory
vector<vector<bool>> match(str.size() + 1, vector<bool>(pattern.size() + 1, false));
match[0][0] = true; // empty str matches empty pattern
for (int i = 1; i <= pattern.size(); ++i) {
if (pattern[i - 1] == '*') {
// don't need to care about the previous match value, it muse be true
// otherwise the loop will break
match[0][i] == true;
} else {
break;
}
}
for (int i = 1; i < str.size(); ++i) {
for (int j = 1; j <= pattern.size(); ++j) {
if (pattern[j - 1] == '*') {
match[i][j] = match[i][j - 1] | match[i - 1][j];
} else if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
match[i][j] = match[i - 1][j - 1];
}
}
}
return match[str.size()][pattern.size()];
}
};