echo

任生命穿梭 时间的角落

0%

正则表达式匹配

Posted on Edited on In Valine:

10. 正则表达式匹配

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

1
2
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

我们每次从字符串 p 中取出一个字符或者字符 + 星号的组合，并在 s 中进行匹配。对于 p 中的一个字符，它只能匹配 s 中的一个字符；对于字符和星号的组合，它可以在 s 中匹配任意个字符。因此，我们考虑使用动态规划，对匹配的方案进行枚举。

我们使用 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。在进行状态转移时，我们考虑 p 的第 j 个字符的匹配情况：

  • 如果 p 的第 j 个字符是一个小写字母，那么必须在 s 中匹配一个相同的小写字母即：

image-20200620105517136

如果 s 的第 i 个字符与 p 的第 j 个字符不同则返回 false，如果它们相同，则匹配结果等于两个字符串前面部分匹配的结果

  • 如果 p 的第 j 个字符是 * ，那么就表示我们可以对 p 的 j-1 个字符匹配任意次。在匹配 0 次的情况下：f[i][j] = f[i][j-2] （直接丢弃这个字母加星号的组合）；在匹配 1 次的情况下：f[i][j] = f[i-1][j-2], if s[i] = p[j-1]；在匹配 2 次的情况下：f[i][j] = f[i-2][j-2], if s[i-1] = s[i] = p[j-1]；在匹配 3 次的情况下：f[i][j] = f[i-3][j-2], if s[i-2] = s[i-1] = s[i] = p[j-1]……

    仔细思考，字母 + 星号只有两种情况：

    • 匹配 s 末尾的一个字符，将该字符扔掉，该组合继续匹配
    • 不匹配字符，将组合扔掉，不再进行匹配

image-20200620111004440

f[i][j] = f[i-1][j], if s[i] = p[j-1] 代表扔掉 s 末尾的一个字符，继续匹配；f[i][j] = f[i][j-2], if s[i] = p[j-1]代表扔掉组合，不再匹配。

最终的状态转移方程如下：

image-20200620111757955
字符串的字符下标是从 0 开始的，在实现上面的状态转移方程时，需要注意状态中每一维下标与实际字符下标的对应关系。

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
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
		//初试化 dp 数组，两个字符串为空时，匹配成功
        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for(int i = 0; i <= m; i++){
            //s 为空，p 不为空情况下，f[0] 全为false
            for(int j = 1; j <= n; j++){
                // p[j] 为 * 号
                if(p.charAt(j - 1) == '*'){
                    // s[i] == p[j-1] ??? 能否匹配字母+星号组合中的字母
                    if(matches(s, p, i, j - 1)){
                        f[i][j] = f[i][j - 2] || f[i - 1][j];
                    }else{
                        //丢弃组合
                        f[i][j] = f[i][j - 2];
                    }
                }else{// p[j] 不为 * 号
                    if(matches(s, p, i, j)){
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
	//判断s[i - 1] 和 p[j - 1]是否相等
    public boolean matches(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);
    }
}

时间复杂度 O(mn)，空间复杂度O(mn)。