正则表达式匹配（详细多解法）

àì夳堔傛蜴生んèń 2023-06-21 07:22 10阅读 0赞

**目录**

•写在前面

•题目

•解法一

•解法二

•解法三

--------------------

# •写在前面 #

所谓真的勇士，敢于直面不用API的手撕，我最开始看到这道题的时候，觉得简直就是到秒杀题，不过我还是按捺住了内心用java正则表达式API的冲动，手撕匹配代码，算法使用的思想就是递归，我最开始是使用直接递归解决了这道题，后面看别人的解法的时候，发现在递归上进行了改进，使用了动态规划的思路，降低了子串创建的时间成本，觉得挺有意思的，就记录下来，毕竟正则表达式我从来没有想过自己去实现过，哈哈哈。

# •题目 #

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
    '.' 匹配任意单个字符
    '*' 匹配零个或多个前面的那一个元素
    所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
    
    说明:
    
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
    示例 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

# •解法一 #

思路其实不难，我们要做的是匹配两个字符串是否相同，在正常匹配下，题目规定了两个特殊字符作为规则，‘.’代表可以匹配任意的字符和‘\*’代表在它前面的一个字符会重复出现0-n次。所以，除了遇到了这两个特殊规则字符之外，其他的都是正常匹配。可能说起来容易，做起来难，我们怎么去实现特殊判断这两个字符呢？很简单，我们只要将正常字符匹配后，继续匹配除开这个字符之外的子串即可，有一种情况要做特殊处理，就是当正在比较的字符的下一个字符是\*时，若两个字符相等，我们只需要移动字符串即可，不移动规则串，当不匹配时，移动规则串，而不移动字符创。可能说起来很干，我直接上代码，在代码里面加入注释进行讲解。

public static boolean isMatchS2(String s, String p) {
            //s为字符串，p规则串
            //首先判断，当字符串和匹配串为空时，直接判断匹配成功
            if(p.isEmpty()) return s.isEmpty();
    
            //上面判断完之后，进一步判断在字符串不为空的前提下，判断字符串的第一个字符是否
            //与规则串的字符相等（注意规则串如果是.也算相等哦），flag为flase不相等，反之相等
            boolean flag = !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
    
            //获得了第一个字符是否相等的标记flag之后，我们需要判断规则串此时的下一个字符是不是
            //特殊字符*，如果是，当flag为flase时，说明第一个字符不匹配，我们只要将规则串跳过*就
            // 行；当flag为true时，说明第一个匹配，我们只要将字符串移动下一个，接着进行匹配就行
            if(p.length() >= 2 && p.charAt(1) == '*'){
                //左右两边只要有一个是true就匹配成功
                return isMatchS2(s, p.substring(2)) || flag && isMatchS2(s.substring(1), p);
            }else{
                //如果规则串没有*,且flag为true,直接字符串和规则串同时移动就行
                return flag && isMatchS2(s.substring(1), p.substring(1));
            }
        }

# •解法二 #

上面的解法其实不够好，因为递归中，每次传入的是子串，所以需要在下一级递归中，创建字符串容纳子串，这样造成了字符串创建开销，那我们有没有什么方法降低创建开销，甚至直接去掉这个开销呢？当然有，我们可以使用动态规划的思想，开一个二维数组，两个下标分别对应字符串和规则串，用于记录是否匹配过即可，然后我们递归的时候传入的就不是子串了，直接将两个字符串传入即可，不过我们需要在递归上多传入当前数组的两个下标（其实就是当前两个字符串匹配到哪了，传入位置）。来，直接上代码，感受一下动态规划思想的魅力。

public static boolean isMatchS3(String s, String p) {
            //这个二维数组用来存对应下标的匹配结果，这样我们在递归中若遇到一样
            // 的直接返回结果就可以了。
            Boolean a[][] = new Boolean[s.length() + 1][p.length() + 1];
            //递归思路和第一种解法差不多，不过我们在递归方法中多传了当前数组的
            // 两个下标（其实就是当前两个字符串匹配到哪了，传入位置）
            return match(a, 0, 0, s, p);
        }
    
        public static boolean match(Boolean[][] a, int i, int j, String s, String p){
            //首先判断二维数组中的结果
            if(a[i][j] != null) return a[i][j];
    
            boolean ans;
            //先判断规则串有没有走完，走完了再判断字符串走完了不，同时走完匹配成功，返回true
            if(j == p.length()){
                ans = i == s.length();
            }else{
                //这里是递归的核心思路，和上面的差不多，不过多了是把结果存在二维数组中
                boolean flag = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                if(j + 1 < p.length() && p.charAt(j + 1) == '*'){
                    ans = match(a, i, j + 2, s, p) || flag && match(a, i + 1, j, s, p);
                }else {
                    ans = flag && match(a, i + 1, j + 1, s, p);
                }
            }
            a[i][j] = ans;
            return ans;
        }

# •解法三 #

如果你觉得递归在栈的使用比较消耗资源，那么也可以直接不用递归，使用非递归结合动态规划思路就可以，这个实际运行起来的时间我就不多说了，反而更大，噗哈哈哈。直接上代码吧

public static boolean isMatchS4(String s, String p){
            boolean[][] datas = new boolean[s.length() + 1][p.length() + 1];
            datas[s.length()][p.length()] = true;
            for (int i = s.length(); i >= 0; i--) {
                for (int j = p.length() - 1; j >= 0; j--) {
                    boolean firstMatch = i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.');
                    if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                        datas[i][j] = datas[i][j + 2] || firstMatch && datas[i + 1][j];
                    } else {
                        datas[i][j] = firstMatch && datas[i + 1][j + 1];
                    }
                }
            }
            return datas[0][0];
        }