【算法攻坚】实现简易正则匹配

发表于

这是我参与11月更文挑战的第13天，活动详情查看：2021最后一次更文挑战

今日题目

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

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

示例 1：

输入：s = “aa” p = “a”
输出：false
解释：”a” 无法匹配 “aa” 整个字符串。

示例 2:

输入：s = “aa” p = “a*“
输出：true
解释：因为 ‘*‘ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3：

输入：s = “ab” p = “.*”
输出：true
解释：”.*” 表示可匹配零个或多个（’*‘）任意字符（’.’）。

示例 4：

输入：s = “aab” p = “c*a*b”
输出：true
解释：因为 ‘*‘ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5：

输入：s = “mississippi” p = “mis*is*p*.”
输出：false

提示：

1 <= s.length <= 20
1 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

思路

如果在实际开发过程中遇到类似的需求可千万别想着自己实现正则匹配

重复造轮子是对前辈的最大不尊敬，各个编程语言都有着现成的正则api，

一行代码就可以搞定：

1
2
3
java复制代码public boolean isMatch(String s, String p) {
    return Pattern.compile(p).matcher(s).matches();
}

执行用时：39 ms, 在所有 Java 提交中击败了10.52%的用户

内存消耗：38.4 MB, 在所有 Java 提交中击败了14.85%的用户

解法

如果遇到算法题，还是要从基本的字符串解析入手，一般也不会让用现成的api

这道题采用前面提到过的动态规划思想去解题

难点无非就是找出状态转移方程和确定始值

首选，定义状态dp[i][j]的含义：

对于字符串 s 和字符规律 p，dp[i][j]: 表示s的前i个字符与p的前j个字符是否匹配，结果用boolean类型表示。

然后，确定状态转移方程（公式）

对于字符串s只会是a-z的字符组成

对于字符规律p会分为三种情况

  1. 全是a-z的字符
  2. 除了字符外包含特殊符号“.”
  3. 除了字符外包含特殊符号“*”

对于第一种情况全是字符的情况最简单只要字符相等即可

1
2
3
4
5
bash复制代码if(s[i] == p[j]){
	dp[i][j] = dp[i - 1][j - 1]
}else{
	dp[i][j] = false; 
}

对于第二种情况包含特殊字符.时，此时的.代表可以匹配任意一个字符，也就说此处无论s的字符是什么都匹配，然后取决于进一步的判断

1
bash复制代码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]不匹配，此时由于*的存在，相当于p[j-1]p[j]没匹配，直接跳过这两个就可以

而且一定要注意p[j-1]一定不能为.不然就不是不匹配了

1
2
3
bash复制代码if(s[i] != p[j-1] && p[j-1] != '.'){
	dp[i][j] = dp[i][j - 2];
}

当s[i]与p[j-1]匹配时，此时要么是s[i]与p[j-1]字符相等(有可能匹配多个s[i-x]= s[i] = p[]j-1)，要么是p[j-1]= “.”匹配了任意字符(只会是两个)

1
bash复制代码dp[i][j] = 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
java复制代码public boolean isMatch(String s, String p) {
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    dp[0][0] = true;
    for (int j = 1; j <= p.length(); j++) {
        if (p.charAt(j - 1) == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 1; j <= p.length(); j++) {
            char si = s.charAt(i - 1), pj = p.charAt(j - 1);
            //全字符场景
            if (Character.isLowerCase(pj)) {
                if (si == pj)
                    dp[i][j] = dp[i - 1][j - 1];
                //包含*    
            } else if (pj == '.') {
                dp[i][j] = dp[i - 1][j - 1];
                //包含.       
            } else {
                char pre_pj = p.charAt(j - 2);
                if (si != pre_pj && pre_pj != '.') {
                    dp[i][j] = dp[i][j - 2];
                } else {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}

小结

动态规划的题目还是挺有规律的，难点就是在找到状态转移方程，然后考虑边界，细心调试就能解出题目，加油！

今天多学一点，明天就少说一句求人的话，加油！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%