[NC]122. 正则表达式匹配

🚩传送门：牛客题目
力扣题目

题目

给你一个字符串 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 解释：“.“ 表示可匹配零个或多个（’*’）任意字符（’.’）。

解题思路：动态规划

👉 定义： 表示的前 个字符与的前 个字符能否匹配 。

表示的是 中的第 个字符，表示的是 中的第 个字符，并非数组下标，切记！

在进行状态转移时，我们考虑的第 个字符的匹配情况：

1. 如果的第 个字符是一个小写字母，那么必须在中匹配一个相同的小写字母，即

1. 如果的第 个字符是一个，那么就可以对的第 个字符可以匹配任意自然数次。

如果我们通过这种方法进行转移，那么我们就需要枚举这个组合到底匹配了主串中的几个字符，会增导致时间复杂度增加，并且代码编写起来十分麻烦。我们不妨换个角度考虑这个问题：**字母***的组合在匹配的过程中，和要么匹配，要么不匹配。

• 对于不匹配的。
• 对于匹配的要么重复 0 次，要么重复任意 X 次。

💥匹配的本质上只会有两种情况：

• 重复 0 次，则将**_字母*_**组合扔掉 。注意此时和一定是匹配的 ，但是不要

  此时

• 重复 _X_ 次，那么必然，字符是匹配的，此时

🚩解释一下为什么，**字母***组合，可以匹配多个主串中的，可能在我们大脑里面模拟时总认为**字母***和是第一次匹配，我们总是想在开始就弄清楚它到底和后面几个匹配上，这样想也正常，但是不好做，我们应该把当前当成与**字母***组合匹配的最后一个结尾，不断的判断它，它会是最后一个匹配的字符吗？

• 如果是，即**X=LastTime**，我们应该怎么办，我们只需要判断，因为要是匹配，必然是匹配的，反之不匹配，不可能匹配。
• 如果它不是最后一个匹配的字符呢，即**X=AnyMidTime**，不重要，因为如果当前想要匹配，那么必然要匹配，反之不匹配，不可能匹配。
• 如果它不是，那么假设当前是和**字母***第一次匹配，即**X=FirstTime**，那么当前是否匹配取决于什么，依旧取决于或。

  为什么？好问题，因为它虽然匹配了，但是有两种选择：

  1. 第一次匹配只匹配 0 次，
  2. 第一次匹配只匹配 1 次，

  但是第一次匹配时，和与去匹配是等价的，因为对于来说最后的可以匹配 0 次。故

综上：对于匹配的我们不清楚到底是匹配 0 次还是匹配 X 次，因此选择

如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：

1. 在任意情况下，只要是 .，那么一定成功匹配中的任意一个小写字母。

其中 判断两个字符是否匹配的辅助函数。只有当 是 .或者 和 本身相同时，这两个字符才会匹配。

🚩综上，状态转移方程：

🚩综上，算法流程：

首先判断的第 个字符是不是

• 如果是，判断和是否相等
  • 相等，（有可能匹配0次，有可能匹配任意次）
  • 不等，
• 如果是或者，判断和是否相等
  • 相等，
  • 不等，

复杂度分析

时间复杂度： ，其中 是字符串长度，其中 是字符串长度。

空间复杂度： ，即为存储所有状态使用的空间。

我的代码

public class Solution {
    // P的第i个元素下标为i-1,S的第j个元素下标为j
    public boolean HelpCheck(String str, String pattern,int i,int j){
        // 传进来的主串是空串,空串不会和任何非空模式串匹配
        if(j==0) return false;
        if(pattern.charAt(i-1)=='.'||pattern.charAt(i-1)==str.charAt(j-1)) 
            return true;
        return false;
    }
    public boolean match (String str, String pattern) {
        //  定义:P 的前 i 个字符是否和 S 的前 j 个字符串匹配
        boolean [][]dp=new boolean[pattern.length()+1][str.length()+1];
        // 空串与空串必定匹配
        dp[0][0]=true;
        // 外层模式串(i=0说明模式串是空串,空串和任何主串都不会匹配)
        for(int i=1;i<dp.length;i++){
            // 内层主串
            for(int j=0;j<dp[0].length;j++){
                // 判断pattern第i个元素是否是*，注意pattern的第i个元素下标是i-1
                if(pattern.charAt(i-1)=='*'){
                    // 先判断是否相等,检查pattern的第i-1个元素与str第j个元素是否相等
                    if(HelpCheck(str,pattern,i-1,j)){
                        // 相等可以匹配 n 次,可以匹配 0 次,从后面想
                        dp[i][j]=(dp[i][j-1]||dp[i-2][j]);
                    }else{ 
                        // 不相等，可以 0 次取消,此时变成p[1,i-2]与S[1,j]比较
                        dp[i][j]=dp[i-2][j];
                    }
                }else{ // 说明pattern第i个元素是 "." 或者字母
                    // 检查P的第i个元素和S的第j个元素是否相等
                    if(HelpCheck(str,pattern,i,j)) dp[i][j]=dp[i-1][j-1];
                    else dp[i][j]=false;
                }
            }
        }
        return dp[pattern.length()][str.length()];
    }
}

解释一下为什么外循环从1开始，而内循环从0开始

• 因为对于模式串来说，任何空的模式串去匹配主串，除非主串空，否则一定不匹配
• 然而对于主串来说，主串空，模式串非空却有可能是匹配的，比如说_P:"a*"_和_S:"a"__