Problem
Given an input string (s
) and a pattern (p
), implement regular expression matching with support for '.'
and '*'
.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
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 = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
Solution
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
var dp = Array(s.length + 1).fill(0).map(_ => Array(p.length + 1));
return helper(dp, 0, 0, s, p);
};
var helper = function (dp, i, j, s, p) {
var res = false;
if (dp[i][j] !== undefined) return dp[i][j];
if (j === p.length) {
res = i === s.length;
} else {
if (i === s.length) {
res = p[j + 1] === '*' && helper(dp, i, j + 2, s, p);
} else if (s[i] === p[j] || p[j] === '.') {
if (p[j + 1] === '*') {
res = helper(dp, i + 1, j, s, p) || helper(dp, i, j + 2, s, p) || helper(dp, i + 1, j + 2, s, p);
} else {
res = helper(dp, i + 1, j + 1, s, p);
}
} else {
res = p[j + 1] === '*' && helper(dp, i, j + 2, s, p);
}
}
dp[i][j] = res;
return res;
};
Explain:
动态规划,dp[i][j]
代表 s[i]
与 p[j]
是否可匹配。
Complexity:
- Time complexity : O(mn).
- Space complexity : O(mn).