吴良超的学习笔记

LeetCode解题报告(10, 44)--正则表达式的匹配与通配符的匹配

正则表达式和通配符均是用来匹配字符串的,但是两者使用的范围不一样,通配符一般用在 Linux 命令行shell中,而正则表达式使用则更加广泛,在各种编程语言和工具中均有支持。下面主要讲述如何实现正则表达式和通配符的简单匹配。

题目选自 LeetCode 的 10. Regular Expression Matching44. Wildcard Matching,之所以说是简单匹配,是因为两者的实现的只是两个符号的功能。正则匹配要求实现 *.的匹配功能,而通配符匹配要求实现?*的匹配。

解决这种两个字符串的比较问题一般可考虑动态规划。以两个字符串的长度分别作为长和宽建立一个二维矩阵,通过二维动态规划解决。

正则表达式

在正则表达式中,.表示任意一个单一字符,*表示0个或若干个前一个字符(表示为0个的时候前一字符也失效,也就是 a* 可以匹配出空字符串)。

首先我们建立了一个 m*n 的dp矩阵,其中m表示匹配模式字符串 p 的长度,n表示待匹配字符串 s 的长度。则 dp[i][j] 表示子字符串 p[:i]s[:j] (均包含i和j)是否匹配(true/false)。假设目前已知 dp[i][j-1] 及其前面的所有情况的匹配关系,那么要求dp[i][j]通过动态规划的递推关系如下:

1
2
3
4
5
1. 假如 p[i] == '.',则dp[i][j] = dp[i-1][j-1]
2. 假如 p[i] == letter(a-zA-Z),则dp[i][j] = dp[i-1][j-1] && (p[i]==s[j])
3. 假如 p[i] == '*',则 dp[i][j] = dp[i-2][j] ||
dp[i-1][j] ||
(dp[i][j-1] && (p[i-1] == s[j]))

上面的1,2 均比较好理解,关键是出现 * 时要分三种情况讨论,分别是 * 匹配了0个,1
个,和若干个前一字符。假如匹配了0个前一字符,那么当前位置的匹配结果与dp[i-2][j]相同;匹配了1个前一字符,则当前位置的匹配结果与 dp[i-1][j] 相同;关键是假如匹配了多个前一字符,该如何判断,此时我们无法知道到底匹配了多少个前一字符,但是换个角度去想这个问题,假如匹配了多个前一字符,那么前一字符要与当前的 s[j] 匹配(p[i-1]==s[j] 或 p[i-1]=’.’),此时要想匹配成功(dp[i][j]为true),则当前的匹配串(p[:i])必须能够匹配s[:j-1],也就是dp[i][j-1]为true。对于这三种情况出现任意一种均可认为匹配,因此取或操作。

在具体实现中还要注意数组越界的问题,可以看到上面出现了 i-1,j-1,i-2的下标,那么在实现的时候要在原二维矩阵中各增加一行和一列,表示第0个字符也就是空字符从而避免了i-1的越界;同时只有在遇到*时才会出现i-2的下标,且这种情况下只有当*出现在匹配串第一个的时候才会越界,而当*出现在匹配串的第一个字符的时候表示为空字符串,除了待匹配字符串为空时一律为false。具体实现的Java代码如下所示:

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
public class Solution 
{

public boolean isMatch(String s, String p)
{

int m = p.length()+1, n = s.length()+1;
boolean[][] dp = new boolean[m][n];
for (int i=0; i<m; i++)
{
for (int j=0;j<n; j++)
{
if(i==0)
{
if(j==0) dp[i][j] = true;
else dp[i][j] = false;
}
else if(j==0)
{
if(p.charAt(i-1)!='*') dp[i][j] = false;
else dp[i][j] = dp[i-1][j] || dp[i-2][j];
}
else
{
if (p.charAt(i-1)=='.') dp[i][j] = dp[i-1][j-1];
else if (p.charAt(i-1) == '*')
{
if (i==1) dp[i][j] = false;
else dp[i][j] = dp[i-2][j] ||
dp[i-1][j] ||
((p.charAt(i-2)== '.' || p.charAt(i-2)==s.charAt(j-1)) && dp[i][j-1]);
}
else dp[i][j] = (s.charAt(j-1)==p.charAt(i-1)) && dp[i-1][j-1];
}
}
}
return dp[m-1][n-1];
}
}

通配符

在通配符中 表示一个字符,而 * 与正则表示式中的含义不一样,在这里 * 表示任意字符串(包括空字符串)。

采用上面的符号(dp,s,p)的定义,在求 dp[i][j],有以下的递推关系

1
2
3
1. 假如 p[i] == '?',则dp[i][j] = dp[i-1][j-1]
2. 假如 p[i] == letter(a-zA-Z),则dp[i][j] = dp[i-1][j-1] && (p[i]==s[j])
3. 假如 p[i] == '*',则 dp[i][j] = dp[i-1][j] || dp[i][j-1]

前面的两种情况都比较好理解,这里的关键点是当遇到 * 时,需要讨论两种情况,第一种是*表示空字符,这时候匹配结果与dp[i-1][j]相同;第二种是*表示任意字符串,这时候假如 dp[i-1][0]dp[i-1][j-1] 有一个为真,则dp[i][j]为真,但是这样遍历的话遇到 * 时会导致时间复杂度变得很大,这时候用到了一个技巧,就是dp[i-1][0]dp[i-1][j-1]的结果已经包含在dp[i-1][j] 中了(根据递推式可知道),所以此时只需要或上dp[i-1][j]即可。

实现时也需要注意越界问题,解决方法同上面提到的添加空字符,具体实现的Java代码如下所示:

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
public class Solution 
{

public boolean isMatch(String s, String p)
{

int m = p.length()+1, n = s.length()+1;
boolean[][] dp = new boolean[m][n];
for (int i=0; i<m; i++)
{
for (int j=0; j<n; j++)
{
if(i==0)
{
if(j==0) dp[i][j] = true;
else dp[i][j] = false;
}
else if(j==0)
{
if(p.charAt(i-1)=='*') dp[i][j] = dp[i-1][j];
else dp[i][j] = false;
}
else
{
if (p.charAt(i-1)=='?') dp[i][j] = dp[i-1][j-1];
else if(p.charAt(i-1)=='*') dp[i][j] = dp[i-1][j] || dp[i][j-1];
else dp[i][j] = (s.charAt(j-1)==p.charAt(i-1)) && dp[i-1][j-1];
}
}
}
return dp[m-1][n-1];
}
}