Leetcode 10：正则表达式匹配
题目： 正则表达式匹配
难度：Hard
知识点：动态规划、递归
按照1xx、2xx的顺序做题，然后发现10也是一个值得记录一下的题目，于是写一下吧。
首先说明一点的是，leetcode官方给出的答案属实是没看懂，我还是自己写一下吧
终于看懂官方的答案了，并且自己写了出来，详见解法2。
解法1
看到这个题目，第一感觉很难想到官解的动态规划思路，感觉递归才是人之常情，这里就先写一下递归的操作吧，当然，下面的递归算不上是最好的算法，同时可以增加dp消除重复字问题。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
class Solution {
char[] arrs;
char[] arrp;
public boolean isMatch(String s, String p) {
arrs = s.toCharArray();
arrp = p.toCharArray();
return dp(0,0);
}
public boolean dp(int indexS, int indexP) {
int m = arrs.length;
int n = arrp.length;
if (indexP == n) return indexS == m;
if (indexS == m) {
if ((n - indexP) % 2 == 1) {
return false;
}
for (; indexP + 1 < n; indexP = indexP + 2) {
if (arrp[indexP + 1] != '*') {
return false;
}
}
return true;
}
boolean res = false;
if (arrs[indexS] == arrp[indexP] || arrp[indexP] == '.') {
if (indexP < n - 1 && arrp[indexP + 1] == '*') {
res = dp(indexS,indexP+2) ||
dp(indexS+1,indexP);
}else{
res = dp(indexS+1,indexP+1);
}
} else {
if (indexP < n - 1 && arrp[indexP + 1] == '*') {
res = dp(indexS, indexP + 2);
} else {
res = false;
}
}
return res;
}
}
|
解法2
还是需要研究一下官方的解决方法，这里做一个简单的记录吧
几个注意的点：
- s字符串需要有前0位（空）的情况，因为前0位可以和特殊的前两位（a*）进行匹配，不能忽略递归结构
- dp中的编号与字符串的index要区分开！！！
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
class Solution {
char[] arrs;
char[] arrp;
boolean[][] ans;
public boolean isMatch(String s, String p) {
arrs = s.toCharArray();
arrp = p.toCharArray();
ans = new boolean[s.length() + 1][p.length() + 1];
ans[0][0] = true;
dp();
return ans[arrs.length][arrp.length];
}
public void dp() {
for (int indexS = 0; indexS <= arrs.length; indexS++) {
for (int indexP = 1; indexP <= arrp.length; indexP++) {
if (arrp[indexP - 1] != '*') {
if (check(indexS - 1, indexP - 1)) {
ans[indexS][indexP] = ans[indexS - 1][indexP - 1];
}
} else {
if (indexP >= 2)
ans[indexS][indexP] = ans[indexS][indexP - 2];
if (check(indexS - 1, indexP - 2)) {
ans[indexS][indexP] = ans[indexS - 1][indexP] || ans[indexS][indexP];
}
}
}
}
}
public boolean check(int indexS, int indexP) {
if (indexS == -1) return false;
if (arrp[indexP] == '.' || arrp[indexP] == arrs[indexS]) {
return true;
}
return false;
}
}
|
很佩服出题人，也佩服能想到这种解法的人！
解法3
1
2
3
4
5
6
7
8
|
class Solution {
public boolean isMatch(String s, String p) {
return s.matches(p);
}
}
|
大大的鄙视！
