正则表达式匹配

【原题】 请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符,而’*’表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但是与”aa.a”和”ab*a”均不匹配 【思路】 这道题写的时候也是磕磕碰碰,主要是要考虑的情况比较多。

public class Solution {
    public boolean matchCore(char[] str,char[] pattern,int strIndex,int patternIndex){
    //str和pattern都刚好完成,则说明可以成功匹配
        if(strIndex==str.length&&patternIndex==pattern.length)
            return true;
//若pattern先于str遍历完,则肯定不能够成功匹配
        if(strIndex!=str.length&&patternIndex>=pattern.length)
            return false;
        //System.out.println("asd"+strIndex+" "+patternIndex);
    //如果str已经遍历完,而pattern还没有遍历完,有可能存在pattern存在a*a*这种情况,*每次都零次匹配
        if(strIndex==str.length&&patternIndex!=pattern.length){
            if(patternIndex+1<pattern.length&&pattern[patternIndex+1]=='*')
                return matchCore(str, pattern, strIndex, patternIndex+2);
            return false;
        }

        if(patternIndex<pattern.length-1&&pattern[patternIndex+1]=='*'){
            //System.out.println(strIndex+" "+patternIndex);
            if(pattern[patternIndex]==str[strIndex]||(pattern[patternIndex]=='.'&&strIndex!=str.length))
            //这一部分原理是编译原理里面的非确定性的有限状态机
                    return matchCore(str, pattern, strIndex+1, patternIndex+2)//移动到下一个元素,‘*’只匹配一次
                            ||matchCore(str, pattern, strIndex+1, patternIndex)//pattern不移动,str移动下一个,说明‘*’匹配多次
                            ||matchCore(str,pattern,strIndex,patternIndex+2);//这种情况了*号一次都不匹配,直接跳过‘*’号和‘*’之前的字母  
                else    return matchCore(str, pattern, strIndex, patternIndex+2);//这里很重要,在不相等的情况下,也可以直接跳过‘*’和其之前的字母

        }
        if(strIndex<str.length&&(pattern[patternIndex]==str[strIndex]||(strIndex!=str.length&&pattern[patternIndex]=='.')))
            return matchCore(str,pattern,strIndex+1,patternIndex+1);
        return false;
        } 
    public boolean match(char[] str, char[] pattern)
    {
        if(str.length==0&&(pattern.length==2&&pattern[1]=='*'))
            return true;
        if(str.length==0&&pattern.length==1&&pattern[0]=='.')
            return false;
       return matchCore(str,pattern,0,0);
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏noteless

[四] java8 函数式编程 收集器浅析 收集器Collector常用方法 运行原理 内部实现

收集器是由四个函数约定构成,它们一起工作,将条目汇集到一个可变的结果容器中,并可选择性地对结果执行最终转换。

30520
来自专栏Android知识点总结

Java总结IO之总集篇

字符流和字节流向来各行其事,很少有交集。 但Reader和Writer有两个奇子,名叫InputStreamReader(男)和OutputStreamWri...

14650
来自专栏小樱的经验随笔

BZOJ 3097: Hash Killer I【构造题,思维题】

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

21760
来自专栏数据结构与算法

P2580 于是他错误的点名开始了

题目背景 XS中学化学竞赛组教练是一个酷爱炉石的人。 他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉...

31770
来自专栏高性能服务器开发

(三)dict哈希结构3

/* This function performs just a step of rehashing, and only if there are * no...

28680
来自专栏函数式编程语言及工具

SDP(9):MongoDB-Scala - data access and modeling

    MongoDB是一种文件型数据库,对数据格式没有硬性要求,所以可以实现灵活多变的数据存储和读取。MongoDB又是一种分布式数据库,与传统关系数据库不同...

39640
来自专栏武培轩的专栏

ConcurrentHashMap源码解析(JDK1.8)

package java.util.concurrent; import java.io.ObjectStreamField; import java.io....

44420
来自专栏HansBug's Lab

3098: Hash Killer II

3098: Hash Killer II Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge S...

30060
来自专栏calmound

UVA 10604 Chemical Reaction(六维dp数组)

题意:有六种不同的试剂,放于试管中,不同的试剂融合其产生的热量不同,且生成的新试剂也不相同,问最后最低温度是多少。 分析:由于只有六种试剂,所以开辟一个六维dp...

37970
来自专栏码匠的流水账

聊聊storm的PartialKeyGrouping

storm-core-1.2.2-sources.jar!/org/apache/storm/grouping/PartialKeyGrouping.java

12230

扫码关注云+社区

领取腾讯云代金券