🌕🌕 剑指 Offer 19. 正则表达式匹配
2022年10月10日
- algorithm
🌕🌕 剑指 Offer 19. 正则表达式匹配
难度: 🌕🌕
问题描述
解法
class Solution {
public boolean isMatch(String s, String p) {
// 思路:
// dp[i][j]
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
// 初始化
dp[0][0] = true;
for(int j = 1; j <= n; j ++) {
char c = p.charAt(j - 1);
if(c == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// dp
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= n; j ++) {
char a = s.charAt(i - 1);
char b = p.charAt(j - 1);
if(b == '.' || b == a) {
dp[i][j] |= dp[i - 1][j - 1];
} else if(b == '*') {
dp[i][j] |= dp[i][j - 2]; // 出现 0 次
dp[i][j] |= dp[i][j - 1]; // 出现 1 次
if(p.charAt(j - 2) == '.' || a == p.charAt(j - 2)) {
dp[i][j] |= dp[i - 1][j];
}
}
}
}
return dp[m][n];
}
}