AcWing 30. 正则表达式匹配
原题链接
困难
dp分析
闫氏DP法分析:
1. 状态表示
1.1 集合
dp[i][j]表示s[0, i-1]和p[0,j-1]是否成功匹配。
之所以用dp[i][j]表示i-1是因为可以少初始化一些内容,或者你用dp[i][j]来表示s[1,i]以及p[1,j],这个看个人习惯。在这里我使用0~i-1的表示方法。
主要分三种情况:
a. p[j] != '*', 且为纯字符匹配和.匹配。dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') && dp[i - 1][j - 1];
b. p[j] == '*',分为*表示0字符和表示任意大于等于1的字符。
* 表示0字符:dp[i][j - 2] // p串去除x.因此p消除该内容后的下标为p[j - 3]对应dp[i][j - 2]
* 表示大于等于1个字符:dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
1.2 属性
集合是否为空
2. 状态计算
java代码
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length(), m = p.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for(int i = 0; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
if(i > 0 && (p.charAt(j - 1) != '*')) {
dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') && dp[i - 1][j - 1];
} else if(p.charAt(j - 1) == '*') {
dp[i][j] = (j > 1 && dp[i][j - 2]) || ( i > 0 && dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
}
}
}
return dp[n][m];
}
}