文章目录
前言
解题思路
暴力递归
斜率优化+记忆化搜索
前言
`
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
样本对应模型
定义二维表
字符串有效性检查
str不能有.和*
exp开头不能是*.两个*不能挨着
public static boolean isValid(char[] s, char[] e) {
// s中不能有'.' or '*'
for (int i = 0; i < s.length; i++) {
if (s[i] == '*' || s[i] == '.') {
return false;
}
}
// 开头的e[0]不能是'*'，没有相邻的'*'
for (int i = 0; i < e.length; i++) {
if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
return false;
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
暴力递归
递归含义:
str从si出发及其后面的所有,能不能被exp从ei出发及其后面的所有配出来
能配出来返回true,否则false
ei下一个位置不是*
如果ei+1不是 * ，就说明我e没有操作空间了。它不能指望后面的 * 把它变没,代表此时si必须能和ei对上
只能是[ei]字符等于[si]字符
要么[ei]字符是 . ,它能够变成一切
ei+1是*
0)变零个
让a*变0个a,后面去匹配
1)变1个a
2)变2个a
3) 3个a
4) 4个a
每一种分支全都走，但有一个走通，直接返回true,所有分支都走不通，返回false,
public static boolean isMatch1(String str, String exp) {
if (str == null || exp == null) {
return false;
}
char[] s = str.toCharArray();
char[] e = exp.toCharArray();
return isValid(s, e) && process(s, e, 0, 0);
}
// str[si.....] 能不能被 exp[ei.....]配出来！ true false
public static boolean process(char[] s, char[] e, int si, int ei) {
if (ei == e.length) { // exp 没了 str？
return si == s.length;
}
// exp[ei]还有字符
// ei + 1位置的字符，不是*
if (ei + 1 == e.length || e[ei + 1] != '*') {
// ei + 1 不是*
// str[si] 必须和 exp[ei] 能配上！
return si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
}
// exp[ei]还有字符
// ei + 1位置的字符，是*!
while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
if (process(s, e, si, ei + 2)) {
return true;
}
si++;
}
return process(s, e, si, ei + 2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
斜率优化+记忆化搜索
f(13, 29)的依赖
f(12, 29)的依赖
f(12, 29)=f(13,29)+f(12,31)
在str中i位置字符和str中i+ 1位置字符它一样的时候就存在这个优化
当我一-个格子有枚举行为的时候，我就观察他已经算过的格子,能不能把枚举行为替代掉,
从而得到一一个使用有限若干个位置的方式来得到这一个格子的值
public static boolean isMatch2(String str, String exp) {
if (str == null || exp == null) {
return false;
}
char[] s = str.toCharArray();
char[] e = exp.toCharArray();
if (!isValid(s, e)) {
return false;
}
int[][] dp = new int[s.length + 1][e.length + 1];
// dp[i][j] = 0, 没算过！
// dp[i][j] = -1 算过，返回值是false
// dp[i][j] = 1 算过，返回值是true
return isValid(s, e) && process2(s, e, 0, 0, dp);
}
public static boolean process2(char[] s, char[] e, int si, int ei, int[][] dp) {
if (dp[si][ei] != 0) {
return dp[si][ei] == 1;
}
boolean ans = false;
if (ei == e.length) {
ans = si == s.length;
} else {
if (ei + 1 == e.length || e[ei + 1] != '*') {
ans = si != s.length && (e[ei] == s[si] || e[ei] == '.') && process2(s, e, si + 1, ei + 1, dp);
} else {
if (si == s.length) { // ei ei+1 *
ans = process2(s, e, si, ei + 2, dp);
} else { // si没结束
if (s[si] != e[ei] && e[ei] != '.') {
ans = process2(s, e, si, ei + 2, dp);
} else { // s[si] 可以和 e[ei]配上
ans = process2(s, e, si, ei + 2, dp) || process2(s, e, si + 1, ei, dp);
}
}
}
}
dp[si][ei] = ans ? 1 : -1;
return ans;
}
