给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明:
s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。 示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:输入: s = "aa" p = "a" 输出: true 解释: 因为 '' 代表可以匹配零个或多个前面的那一个元素,
在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。 示例 3:输入: s = "ab" p = "." 输出: true 解释: "." 表示可匹配零个或多个('*')任意字符('.')。
引用来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/regular-expression-matching
很可惜*
的不能够单独依赖前置条件就能判断,有abccccd.跟__abc*cd__这种情况.所以终究要把多种符合匹配规则多种状态都记录下来,然后构建动态方程.
dpi 表示 s 的前 i 个是否能被 p 的前 j 个匹配
因为需要前置条件作为辅助,所以s可p为空都是符合条件的状态,而为空时候的状态我们要手动添加
- S为空,P为空状态成立
- S为空时,P不为空时,只有P为
*
的时候可以通过*
消除前一个字符的规则获得到dp0的状态,其他都是false - S不为空,P不为空时,肯定为false
动态方程初始值建立.然后考虑状态迁移:
对于S = [0,0] 到 S = [0,S.length] 中每一种状态我们都要计算出相应P = [0,0] 到 P = [0,P.length] 时与之对应的状态,因为每种状态都可能为之后判定的前置条件
对于一个新正则值P[j] 为如果P[j]为字符,有P[j] == S [i] 则dpi = dpi
否则dpi == false ;光一个字符成立了没用,之前也成立才是true
对于一个新正则值P[j] 为如果P[j]为.
则dpi = dpi 否则dpi == false ;
对于一个新正则值P[j] 为如果P[j]为*
就要判定*
之前的那个字符和当前的S[i]
如果不相等通过*
消除前一个字符的规则获得到dp0的状态,其他都是false
如果相等.
- dpI是True的话那dpI肯定就是True aa —> a*
- dpI是False 的话那dpI肯定就是False么?不,因为
*
可以删除一个,所以dpI为True的话也能为True ab —> abc* - 还有一种情况是dpi-1为true的话,那dpI肯定就是True aa —> aa*
最后return dp[s.length][p.length];
即可
var isMatch = function (s, p) {
var dp = Array.from(new Array(s.length + 1), () => {
return new Array(p.length + 1)
}); // 构建状态数组+1 因为存在空的情况做前置状态
// dp[x][y] 代表s的前x位是否和p的前y位匹配
dp[0][0] = true; // 空匹配空成立
for (var i = 1; i <= p.length; i++) { //从一开始匹配
if (p[i - 1] == '*') { //对于空字符串匹配只有*可以等同前一个状态,其他的都是错误
dp[0][i] = dp[0][i - 2]
} else {
dp[0][i] = false;
}
}
if (s.length >= 1) {
for (var i = 1; i <= s.length; i++) {
dp[i][0] = false;
}
}
for (var i = 1; i <= s.length; i++) {
for (var j = 1; j <= p.length; j++) {
switch (p[j - 1]) {
case '.':
dp[i][j] = dp[i - 1][j - 1]
break;
case '*':
if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
dp[i][j] = dp[i][j - 1] || //只多一个* 的情况成立条件是去掉这个*也能匹配
dp[i - 1][j] || // 一个匹配字符加个* 的情况成立条件是前一个字符也能匹配
dp[i][j - 2] // 不匹配字符加个* 的情况成立条件是去掉不匹配字符和*能匹配
} else {
dp[i][j] = dp[i][j - 2] // *消除前一个字符
}
break;
default:
if (s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = false;
}
break;
}
}
}
return dp[s.length][p.length];
}