【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】

🚀 算法题 🚀

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

🚀 算法题 🚀

【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】

🚩 题目链接

44. 通配符匹配

⛲ 题目描述

给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够完全匹配输入字符串（而不是部分匹配）。

示例 1：

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

输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：

输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

提示：

0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、‘?’ 或 ‘*’ 组成

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

⚡ 暴力法

🥦 求解思路

简单概括题目的意思:按照给定的规则[规则题目已经给规定好了]，看字符串s是否可以匹配字符串p，如果可以的话，直接返回true，否则，返回false。
这个题目怎么求解呢，我们可以直接根据题的要求来找思路，首先，如果此时俩个位置对应的字符是相等的或者 p位置对应的字符是’?‘，那么同时向后移动一个单位继续向后匹配；其次，如果p当前位置的字符是’*‘,那么此时可以俩种情况，第一种情况是p位置的’*‘匹配了s位置之前的字符，此时s可以继续向后判断，看看此时p位置的’*‘是否还可以继续判匹配，当然这个只是一种情况，还有一种情况就是当前的’*'只匹配s前的字符，，
有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

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(i>=arr1.length&&j>=arr2.length){
            return true;
        }
        if(i>=arr1.length){
            while(j<arr2.length && arr2[j]=='*'){
                j++;
            }
            if(j<arr2.length) return false;
            else return true;
        }
        if(j>=arr2.length) return false;
        boolean flag=false;
        if(arr1[i]==arr2[j]||arr2[j]=='?'){
            flag|=process(i+1,j+1,arr1,arr2);
        }else if(arr2[j]=='*'){
            flag|=process(i+1,j,arr1,arr2)|process(i,j+1,arr1,arr2);
        }
        return flag;
    }
}

🥦 运行结果

暴力超出时间限制，我们继续更新改正！

【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】

⚡ 记忆化搜索

🥦 求解思路

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

🥦 实现代码

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][n];
        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(i>=arr1.length&&j>=arr2.length){
            return true;
        }
        if(i>=arr1.length){
            while(j<arr2.length && arr2[j]=='*'){
                j++;
            }
            if(j<arr2.length) return false;
            else return true;
        }
        if(j>=arr2.length) return false;
        if(dp[i][j]!=-1) return dp[i][j]==1;
        boolean flag=false;
        if(arr1[i]==arr2[j]||arr2[j]=='?'){
            flag|=process(i+1,j+1,arr1,arr2);
        }else if(arr2[j]=='*'){
            flag|=process(i+1,j,arr1,arr2)|process(i,j+1,arr1,arr2);
        }
        dp[i][j]=flag?1:0;
        return flag;
    }
}

🥦 运行结果

通过缓存，将重复计算的结果缓存下来，通过。
时间情况
【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】

空间情况
【LeetCode: 44. 通配符匹配 | 暴力递归=＞记忆化搜索=＞动态规划】

⚡ 动态规划

🥦 求解思路

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

🥦 实现代码

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 j=n-1;j>=0;j--){
            if(arr2[j]=='*'){
                dp[m][j]=true;
            }else{
                break;
            }
        }
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                boolean flag=false;
                if(arr1[i]==arr2[j]||arr2[j]=='?'){
                    flag|=dp[i+1][j+1];
                }else if(arr2[j]=='*'){
                    flag|=dp[i+1][j]|dp[i][j+1];
                }
                dp[i][j]=flag;
            }
        }
        return dp[0][0];
    }

}