source: https://leetcode.com/problems/wildcard-matching/
C/C++ Solution to LeetCode problem 44. Wildcard Matching.
Problem
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).
Examples
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 <= 2000
s
contains only lowercase English letters.p
contains only lowercase English letters,'?'
or'*'
.
Solution
This problem can be solved with Dynamic Programming:
- First we clean the pattern string (remove the extra consecutive
'*'
). - We use two indexes to track what character of the pattern and string we are matching.
- If the indexes are at the end of the pattern and string, then we found a match.
- If only the index of pattern is at the end, there was no match.
- If the pattern at the current index has
'*'
we have three options:- Move index of pattern.
- Move index of string.
- Move both indexes.
- Else if the char at the pattern and string are equal, or the pattern has a
?
, then we can move to next position in both indexes. - Else, there is no match.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private:
string s;
string p;
vector<vector<int>> dp;
void cleanPattern() {
int l=0;
for (int i=0; i<p.size(); i++) {
if (i>0 && p[i] == p[i-1] && p[i] == '*')
continue;
if (l != i)
p[l] = p[i];
l++;
}
p.resize(l);
}
public:
bool compare(int i, int j) {
if (dp[i][j] != -1)
return dp[i][j];
if (i>=s.size() && j>=p.size())
return true;
if (j>=p.size())
return false;
bool m = i<s.size() && (s[i] == p[j] || p[j] == '?');
if (p[j] == '*')
dp[i][j] = compare(i, j+1) || (i<s.size() && (compare(i+1, j+1) || compare(i+1, j)));
else if (m)
dp[i][j] = compare(i+1, j+1);
else
dp[i][j] = false;
return dp[i][j];
}
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
cleanPattern();
dp = vector(this->s.size() + 1, vector(this->p.size() + 1, -1));
return compare(0, 0);
}
};