复制代码
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70// 这题能知道状态是怎么定义: // 常规套路 dp[i][j] 表示s串前[0,i]与p串前[0,j]匹配结果 // 但状态不知如何跳转: // 但有一种跳转一定知道, 那就是当 s[i] == p[j] 时即: // s[i] == p[j] || p[j] == '.' 时, 毫无疑问 // dp[i][j] == dp[i - 1][j - 1] // 当s[i] != p[j]时 该如何呢? // 这里想了很久没想明白,之后到处去看看大牛们的解法 // 能意识到*的特殊,但没联想到还要考虑*前面一个字符,当然如果做多了的话会想到 // 但...本人就是这么菜...对不起 // 当p[j] == '*' 时, 如果 p[j - 1] != s[i] 且 p[j - 1] != '.' 即 // s[i]无法与p[j - 1]*这种形式匹配, 则: // dp[i][j] = dp[i][j - 2]; (因为*可以表示前面字母出现0次) // 否则: s[i] 可以与p[j - 1]*这种形式进行匹配 ,那么具体匹配的形式有以下三种: // dp[i][j] = dp[i - 1][j] // 将s[i] 与 * 匹配,即大佬所说的匹配多个相同字符 // || dp[i][j - 1] // 忽略* 匹配0个 // || dp[i][j - 2]; // 忽略p[j - 1]*, // 三种情况任意一种能匹配上最终都能匹配上 // 最后注意边界条件: // 因为方便边界定义想从1开始,即 // dp[i][j] 表示s[0, i - 1]与p[0, j - 1]匹配结果 // 则边界dp[0][0] = true 表示 "" 与 "" 能匹配 // 另外注意: // 因为p如果是 a*P(P表示字符串) 这样的模式的话, a*可以匹配空串 // 所以有dp[0][i] = dp[0][i - 2]这样的初始化条件 // DP三板斧: 状态, 转移函数, 边界条件 // 三者缺一不可,即使不会做,但看大牛们的解法,一定要都懂的其中的所以然 class Solution { public boolean isMatch(String s, String p){ int n = s.length(); int m = p.length(); boolean[][] dp = new boolean[n + 1][m + 1]; for (int i = 0;i <= n; i++) for (int j = 0; j <= m; j++) dp[i][j] = false; dp[0][0] = true; if (m > 1){ for (int i = 1;i < m; i += 2) if (p.charAt(i) == '*') dp[0][i + 1] = dp[0][ i - 1]; } for (int i = 1;i <= n;i ++){ for (int j = 1;j <= m;j ++){ if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') dp[i][j] = dp[i - 1][j - 1]; else if (j > 1 && p.charAt(j - 1) == '*'){ if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') dp[i][j] = dp[i][j - 2]; else { dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2]; } } } } return dp[n][m]; } }
最后
以上就是紧张大米最近收集整理的关于LeetCode 10 正则表达式匹配 二维dp的全部内容,更多相关LeetCode内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复