【LeetCode: 10. 正则表达式匹配 | 暴力递归=＞记忆化搜索=＞动态规划】网站首页 技术杂谈

【LeetCode: 10. 正则表达式匹配 | 暴力递归=＞记忆化搜索=＞动态规划】

硕风和炜 2024-06-17 11:28:16

简介【LeetCode: 10. 正则表达式匹配 | 暴力递归=＞记忆化搜索=＞动态规划】

在这里插入图片描述

? 算法题 ?

? 算法刷题专栏 | 面试必备算法 | 面试高频算法 ?
? 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
? 作者简介：硕风和炜，CSDN-Java领域优质创作者?，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享???
? 恭喜你发现一枚宝藏博主,赶快收入囊中吧?
? 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？??

? 算法题 ?

在这里插入图片描述

? 目录

? 题目链接

10. 正则表达式匹配

⛲ 题目描述

给你一个字符串 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 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

? 求解思路&实现代码&运行结果

⚡ 暴力法

? 求解思路

再学习这道题题目之前，大家可以先去看一下我另一道和这个题目非常相似的题目，通配符匹配的题解，再来学习这道题目就会非常容易。【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】
简单概括题目的意思:按照给定的规则[规则题目已经给规定好了]，看字符串s是否可以匹配字符串p，如果可以的话，直接返回true，否则，返回false。
这个题目和通配符匹配最大的不同就在于，通配符匹配问题的’*‘可以匹配任意字符，而这道题目的’*'只可以匹配匹配零个或多个前面的那一个元素。弄明白这个区别，那么这道题就迎刃而解了。
具体匹配过程如下:
第一种情况，如果两个字符相同，或者模式串当前是’*'.，则匹配成功，然后继续递归比较i+1和j+1 ;
第二种情况:如果模式串后面跟了""，这又分为两种情况：
(1)如果arr1[i]和arr2[j]相等(比如aa和a*这种情况)，选择匹配前一个字符的零次，也就是直接忽略a，从i和j+2继续递归；当然也可以匹配前一个继续的多次，先将字符串中的a忽略掉，继续递归i+1和j继续向后判断;
(2)如果arr1[i]和arr2[j]不等(比如aa和b这种情况)，则将b忽略掉，继续递归比较i和j+2的过程；
有了基本的思路，接下来我们就来通过代码来实现一下。

? 实现代码

class Solution {
    public boolean isMatch(String s, String p) {
        char[] arr1=s.toCharArray();
        char[] arr2=p.toCharArray();
        return process(0,0,arr1,arr2);
    }

    public boolean process(int i,int j,char[] arr1,char[] arr2){
        if(j>=arr2.length) return i>=arr1.length;
        boolean flag=false;
        if(j+1<arr2.length&&arr2[j+1]=='*'){
            if(i<arr1.length&&(arr1[i]==arr2[j]||arr2[j]=='.')){
                flag|=process(i+1,j,arr1,arr2)|process(i,j+2,arr1,arr2);
            }else{
                flag|=process(i,j+2,arr1,arr2);
            }
        }else{
            if(i<arr1.length&&(arr1[i]==arr2[j]||arr2[j]=='.')){
                flag|=process(i+1,j+1,arr1,arr2);
            }
        }
        return flag;
    }
}

? 运行结果

时间复杂度
在这里插入图片描述

空间复杂度
在这里插入图片描述

⚡ 记忆化搜索

? 求解思路

因为在递归的过程中，会重复的出现一些多次计算的结果，我们通过开辟一个数组，将结果提前缓存下来，算过的直接返回，避免重复计算，通过空间来去换我们的时间。

? 实现代码

class Solution {

    int[][] dp;

    public boolean isMatch(String s, String p) {
        char[] arr1=s.toCharArray();
        char[] arr2=p.toCharArray();
        int m=arr1.length,n=arr2.length;
        dp=new int[m+1][n+1];
        for(int i=0;i<=m;i++) Arrays.fill(dp[i],-1);
        return process(0,0,arr1,arr2);
    }

    public boolean process(int i,int j,char[] arr1,char[] arr2){
        if(j>=arr2.length) return i>=arr1.length;
        if(dp[i][j]!=-1) return dp[i][j]==1;
        boolean flag=false;
        if(j+1<arr2.length&&arr2[j+1]=='*'){
            if(i<arr1.length&&(arr1[i]==arr2[j]||arr2[j]=='.')){
                flag|=process(i+1,j,arr1,arr2)|process(i,j+2,arr1,arr2);
            }else{
                flag|=process(i,j+2,arr1,arr2);
            }
        }else{
            if(i<arr1.length&&(arr1[i]==arr2[j]||arr2[j]=='.')){
                flag|=process(i+1,j+1,arr1,arr2);
            }
        }
        dp[i][j]=flag?1:0;
        return flag;
    }
}

? 运行结果

通过缓存，将重复计算的结果缓存下来，通过。
时间情况
在这里插入图片描述

空间情况
在这里插入图片描述

⚡ 动态规划

? 求解思路

有了递归，有了记忆化搜索，接下来就是动态规划了，直接上手。

? 实现代码

class Solution {

    boolean[][] dp;

    public boolean isMatch(String s, String p) {
        char[] arr1=s.toCharArray();
        char[] arr2=p.toCharArray();
        int m=arr1.length,n=arr2.length;
        dp=new boolean[m+1][n+1];
        dp[m][n]=true;
        for(int i=m;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                boolean flag=false;
                if(j+1<arr2.length&&arr2[j+1]=='*'){
                    if(i<arr1.length&&(arr1[i]==arr2[j]||arr2[j]=='.')){
                        flag|=dp[i+1][j]|dp[i][j+2];
                    }else{
                        flag|=dp[i][j+2];
                    }
                }else{
                    if(i<arr1.length&&(arr1[i]==arr2[j]||arr2[j]=='.')){
                        flag|=dp[i+1][j+1];
                    }
                }
                dp[i][j]=flag;
            }
        }
        return dp[0][0];
    }
}