正则表达式匹配

LeetCode-10. 正则表达式匹配匹配,题目内容如下:

1
2
3
4
5
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

由于题目是要求以正则串来匹配,那么我们以正则串为主,根据正则串的每个字符选择相应的策略来匹配需要匹配的字符串。题解中给出的是正则表达式匹配题解。关于动态规划算法,是一个比较难以理解的算法,通过查阅资料和习题练习,有助于掌握动态规划算法的思想。学习动态规划之前不能一蹴而就,直接上手动态规划,应该从简单的开始,斐波那契数列就是一个很好的例子,最开始使用递归,然后分析递归中的每一个步骤,可以发现很多步骤都是重复计算的过程,因此进行优化,变成记忆化+递归,然后再尝试去转换成动态规划。

回到这道题本身,我们在匹配的时候,先以最简单的问题开始,不考虑特殊规则时,是逐字匹配。以匹配串和正则串为x轴和y轴,建立一个二维数组,每一个字符互相对应一个格子,如果某个字母与上面的能够匹配上,并且前面的串已经匹配成功,因此前面的串加上这个字符仍然能够完全匹配。以最简单的两个单字符匹配为例,如图:

单字符情况
单字符情况

起始状态设置为空串,两个空串是能够匹配的,因此第一个位置是true,而空串不能够与任意字符匹配,因此第一行与第一列的其他均为false。那么在匹配当前字符时,发现这两个字符相同,并且这两个字符之前的串是完全匹配的,即dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1),因此在上图留空的位置应该为true,所以a == a,答案显而易见,但是我们可以通过这样的思路来解决正则表达式匹配的问题。

不难发现,这个动态规划的二维数组里面存储的是s串中前i项与p串中前j项是否可以匹配,这就是动态规划中的状态。接下来我们需要通过题设的条件,找出根据前面状态计算后面状态的方法,这种方法即是状态转移方程。剩下的就是处理动态规划的边界值问题了。

在这道题中通过前面的分析,再对题设条件找出对应的几种情况的状态转移方程。

  • .能够匹配任意单个字符,那么遇到这个符号,都属于可以匹配,因此这个符号为必定匹配,将其归至其他匹配的判断中。
  • *的情况需要考虑两个因素,前一个字符不匹配的情况和多个字符匹配的情况。首先考虑前一个字符不匹配,那么有了这个星号,只要前面的是匹配的,则这个不匹配字符可以忽略,即dp[i][j - 2]。考虑多个字符匹配的情况,s串中的当前字符与p串星号前一个字符匹配,并且s串中前面的串或者前一个字符能够匹配上,则这个字符也能匹配,即dp[i - 1][j] || dp[i][j - 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
32
33
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];
dp[0][0] = true;
for(int i = 0; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2];
if(match(s, p, i, j - 1)) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else {
if(match(s, p, i, j)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[n][m];
}

private boolean match(String s, String p, int i, int j) {
if(i == 0) {
return false;
}
if(p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}

学习到现在,对动态规划有了一定的了解,也能够大概的分析出状态,但是在具体实现过程中仍然存在一定的困难,需要通过题解的帮助才能完成解答。接下来需要逐渐减少对题解的依赖,独立完成动态规划题目的分析和实现。