正则表达式匹配

【原题】 请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符,而’*’表示它前面的字符可以出现任意次(包含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 条评论
登录 后参与评论

相关文章

来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4
来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

1831
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

8175
来自专栏linux驱动个人学习

ALSA声卡驱动的DAPM(一)-DPAM详解

最近使用tinymix 调试相应的音频通道,但是一直不知道音频通道的原理是什么。所以百度了一下,百度结果是与DPAM有关。 一、DAPM简介:  DAPM是Dy...

5196
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1482
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2349
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2762
来自专栏一个会写诗的程序员的博客

《MongoDB极简教程》第二章 MongoDB 基本命令(Shell)

MongoDB的所有请求都以命令的形式发出,支持的命令列表参考Database Commands

944
来自专栏从零开始的linux

mongodb分片

分别在三台机器上面创建 mkdir -pv /data/mongodb/mongos/log mkdir -pv /data/mongodb/config/{d...

4084
来自专栏pangguoming

API手册 常用功能

directive [ng] a form input input [checkbox] input [email] input [number] input ...

3239

扫码关注云+社区