背景
在刷一道Leetcode题
剑指 Offer 19. 正则表达式匹配
对照了答案，使用了DP对此题进行求解，由于没有完全抄题解的，所以有部分内容不完全一致。
但是就逻辑上和题解完全一致。可就是无法通过OJ
源代码
官方题解
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
| class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for(int i = 0;i <= m; i++) {
for(int j = 1;j <= n; j++) {
if(p.charAt(j - 1) == '*') {
if(matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 2))) {
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2];
}
} else {
if(matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 1))) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
public boolean matches(char a,char b) {
if(a == -1) {
return false;
}
if(b == '.') {
return true;
} else {
return a == b;
}
}
}
|
解决思路
1
2
3
4
5
6
7
8
9
10
11
| if(p.charAt(j - 1) == '*') {
if(matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 2))) {
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2];
}
} else {
if(matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 1))) {
dp[i][j] = dp[i - 1][j - 1];
}
}
|
很容易得出结论，问题可能不是在状态转移方程上
然而match函数就这么短，逻辑基本上就等同于没有，我还能写错？
所以正是因为这可怜的自信，这问题差不多花了我10来分钟。
1
2
3
4
5
6
7
8
9
10
| public boolean matches(char a,char b) {
if(a == -1) {
return false;
}
if(b == '.') {
return true;
} else {
return a == b;
}
}
|
问题出现在char的类型转换
match函数在代码中有两次调用
1
2
| matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 2));
matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 1));
|
按理i == 0时 char 即为 (char) -1
依据如下代码段，所以match函数应该返回false
1
2
3
| if(a == -1) {
return false;
}
|
可是并不会，因为**(char) -1 != -1**
1
2
| System.out.println(-1 == (char)-1);
System.out.println((char) -1);
|
char的大小为2个字节，即16位二进制
-1所对应的原码为
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
不难想到将(char) -1 转为int的值即为65535了，这很明显不会与(int)-1相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public class Test {
public static void main(String[] args) {
System.out.println((long) ((short) -1));
System.out.println((long) ((byte) -1));
System.out.println((long) ((int) -1));
System.out.println((long) ((float) -1));
System.out.println((long) ((double) -1));
System.out.println((int) ((char) -1));
}
}
|
最后修改了matches方法，OJ通过了
时间: 2 ms
击败: 40.72%
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
| class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for(int i = 0;i <= m; i++) {
for(int j = 1;j <= n; j++) {
if(p.charAt(j - 1) == '*') {
if(matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 2))) {
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2];
}
} else {
if(matches(i == 0 ? (char)-1 : s.charAt(i - 1),p.charAt(j - 1))) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
public boolean matches(char a,char b) {
if(a == (char)-1) {
return false;
}
if(b == '.') {
return true;
} else {
return a == b;
}
}
}
|
代码优化
时间: 1 ms
击败: 100%
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
| class Solution {
public boolean isMatch(String s, String p) {
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++) {
if(p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
for(int i = 1;i <= m; i++) {
for(int j = 1;j <= n; j++) {
if(p.charAt(j - 1) == '*') {
if(matches(s.charAt(i - 1),p.charAt(j - 2))) {
dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
} else {
dp[i][j] = dp[i][j - 2];
}
} else {
if(matches(s.charAt(i - 1),p.charAt(j - 1))) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
public boolean matches(char a,char b) {
if(b == '.') {
return true;
} else {
return a == b;
}
}
}
|
复盘
很多东西不是我们认为他是他们他就是怎样的，一切都要以实际结果为主。
即使你认为再理所当然的东西，脱离了实际都将不复存在。
