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

发表于 标签 ， ，

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

题目选自 LeetCode 的 10. Regular Expression Matching 和 44. 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];
    }
}