Problem
Given an input string (s
) and a pattern (p
), implement wildcard pattern matching with support for '?'
and '*'
.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
s
could be empty and contains only lowercase lettersa-z
.p
could be empty and contains only lowercase lettersa-z
, and characters like?
or*
.
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'.
Example 4:
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input:
s = "acdcb"
p = "a*c?b"
Output: false
Solution
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
var dp = Array(p.length + 1).fill(0).map(_ => ({}));
return test(s, p, 0, 0, dp);
};
var test = function (s, p, sIndex, pIndex, dp) {
if (dp[pIndex][sIndex] !== undefined) return dp[pIndex][sIndex];
var sNow = s[sIndex];
var pNow = p[pIndex];
var res = false;
if (pNow === undefined) return sNow === undefined;
if (sNow === undefined) {
for (var i = pIndex; i < p.length; i++) {
if (p[i] !== '*') return false;
}
return true;
}
if (sNow === pNow || pNow === '?') {
res = test(s, p, sIndex + 1, pIndex + 1, dp);
} else if (pNow === '*') {
res = test(s, p, sIndex, pIndex + 1, dp) || test(s, p, sIndex + 1, pIndex + 1, dp) || test(s, p, sIndex + 1, pIndex, dp);
}
dp[pIndex][sIndex] = res;
return res;
};
Explain:
dp[i][j]
代表当正则第 i
位匹配字符串第 j
位时,是否 match.
Complexity:
- Time complexity : O(m*n).
- Space complexity : O(m*n).