首页 > 其他分享 >10. 正则表达式匹配

10. 正则表达式匹配

时间:2023-03-17 10:57:23浏览次数:52  
标签:10 return charAt 正则表达式 substring length isMatch 匹配 false

10. 正则表达式匹配

1.动态规划

    public boolean isMatch(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();

        // dp[i][j]:表示s的前i个字符,p的前j个字符是否能够匹配
        boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];

        // 初期值
        // s为空,p为空,能匹配上
        dp[0][0] = true;
        // p为空,s不为空,必为false(boolean数组默认值为false,无需处理)

        // s为空,p不为空,由于*可以匹配0个字符,所以有可能为true
        for (int j = 1; j <= cp.length; j++) {
            if (cp[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 填格子
        for (int i = 1; i <= cs.length; i++) {
            for (int j = 1; j <= cp.length; j++) {
                // 文本串和模式串末位字符能匹配上
                if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (cp[j - 1] == '*') { // 模式串末位是*
                    // 模式串*的前一个字符能够跟文本串的末位匹配上
                    if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
                        dp[i][j] = dp[i][j - 2]      // *匹配0次的情况
                                || dp[i - 1][j];     // *匹配1次或多次的情况
                    } else { // 模式串*的前一个字符不能够跟文本串的末位匹配
                        dp[i][j] = dp[i][j - 2];     // *只能匹配0次
                    }
                }
            }
        }
        return dp[cs.length][cp.length];
    }

2.递归

    // 递归写法
    public boolean isMatch(String s, String p){
        if (s.length()==0 ){
            if (p.length()==0){
                return true;
            }
            if (p.charAt(p.length()-1)!='*'){
                return false;
            }else{
                return isMatch(s,p.substring(0,p.length()-2));
            }
        }else if(p.length()== 0){
            return false;
        }

        if(s.charAt(s.length()-1) == p.charAt(p.length()-1) || p.charAt(p.length()-1) == '.'){
            return isMatch(s.substring(0,s.length()-1),p.substring(0,p.length()-1));
        }else if(p.charAt(p.length()-1) == '*'){
            if(s.charAt(s.length()-1) == p.charAt(p.length()-2) || p.charAt(p.length()-2) == '.'){
                return isMatch(s,p.substring(0,p.length()-2)) || isMatch(s.substring(0,s.length()-1),p.substring(0,p.length()-2)) || isMatch(s.substring(0,s.length()-1),p);
            }else{
                return isMatch(s,p.substring(0,p.length()-2));
            }
        }else{
            return false;
        }
    }

思路:
{{uploading-image-753426.png(uploading...)}}
转载:https://leetcode.cn/problems/regular-expression-matching/solutions/296114/shou-hui-tu-jie-wo-tai-nan-liao-by-hyj8/
参考:https://www.bilibili.com/video/BV1jd4y1U7kE/?spm_id_from=333.337.search-card.all.click&vd_source=136c403361d2786d99be256b33ac445a

标签:10,return,charAt,正则表达式,substring,length,isMatch,匹配,false
From: https://www.cnblogs.com/chenyi502/p/17225794.html

相关文章

  • PAT Basic 1031. 查验身份证
    PATBasic1031.查验身份证1.题目描述:一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下:首先对前17位数字加权求和,权重分配......
  • 代码随想录17 | 104.二叉树的最大深度 | 222.完全二叉树的节点个数 | 104.二叉树的最
    110. 平衡二叉树给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。算......
  • ASEMI代理MIMXRT1064CVJ5B原装现货NXP车规级MIMXRT1064CVJ5B
    编辑:llASEMI代理MIMXRT1064CVJ5B原装现货NXP车规级MIMXRT1064CVJ5B型号:MIMXRT1064CVJ5B品牌:NXP/恩智浦封装:LFGBA-196批号:2023+安装类型:表面贴装型引脚数量:196类型......
  • shell-创建YYYY-MM-DD格式目录,当前日期之前的365天每天创建一个目录,每个目录下创建10
    创建YYYY-MM-DD格式目录,当前日期之前的365天每天创建一个目录,每个目录下创建10个.log后缀的文件#!/bin/bash#descriptionforiin{1..365}dofile_dir=/opt/`d......
  • PCB布局-整板扇出-拉线-10
      布局:固定的器件先放置好优先摆放重要的功能的模块,然后是次要的好的布局为后期走线准备,考虑走线通道dc电容都是先大后小摆放,进小靠近元件,出大靠近元件,先过滤低频,......
  • LeetCode1024 -- 二分
    1.题目描述查找满足劳累天数严格大于不劳累天数的最大子区间2.思路对于区间问题,很容易先想到前缀和帮助我们优化。我们可以设,劳累=\(1\),不劳累=\(-1\),那么,就是求......
  • PAT 甲级 1012 The Best Rank(25)
    ToevaluatetheperformanceofourfirstyearCSmajoredstudents,weconsidertheirgradesofthreecoursesonly:C-CProgrammingLanguage,M-Mathematics......
  • 【洛谷】P2480 [SDOI2010]古代猪文
    原题链接题意求:\[g^{\sum_{d|n}\binom{n}{d}}\mod999911659\]\(n,g\leq10^9\)。思路:因为\(999911659\)是质数,由欧拉定理的推论,可以得到:\[g^{\sum_{d|n}\bino......
  • PAT Basic 1030. 完美数列
    PATBasic1030.完美数列1.题目描述:给定一个正整数数列,和正整数\(p\),设这个数列中的最大值是\(M\),最小值是\(m\),如果\(M≤mp\),则称这个数列是完美数列。现在给定......
  • 剑指 Offer II 010. 和为 k 的子数组
    剑指OfferII010.和为k的子数组给定一个整数数组和一个整数k,请找到该数组中和为k的连续子数组的个数。示例1:输入:nums=[1,1,1],k=2输出:2解释:此题......