正则表达式匹配

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

相关文章

来自专栏有困难要上,没有困难创造困难也要上!

Python 使用 os.fork() 创建子进程

3376
来自专栏海天一树

小朋友学Python(18):目录

Python的os模块有许多方法能帮你创建,删除和更改目录。 一、创建目录 mkdir()方法 可以使用os模块的mkdir()方法在当前目录下创建新的目录们。...

2726
来自专栏深度学习之tensorflow实战篇

python文件打开方式详解——a、a+、r+、w+区别

第一步 排除文件打开方式错误: r只读,r+读写,不创建 w新建只写,w+新建读写,二者都会将文件内容清零 (以w方式打开,不能读出。w+可读写) **w+与r...

3797
来自专栏coder修行路

python成长之路-----day1-----作业(登录程序和三级菜单)

作业: 作业1:用户登录 1)程序说明: a.用户输入密码验证成功然后打印欢迎信息 b.如果密码错误,用户登录失败,提示用户,密码错误 c.用户输入密码错误3次...

1769
来自专栏深度学习之tensorflow实战篇

mysql、mongodb、python(dataframe).聚合函数的形式,以及报错解决方案

1、mysql select * from table_name group by name,id 有的时候执行下面语句报错sql_mode=only_ful...

2844
来自专栏10km的专栏

powershell:脚本中检查mingw-w64编译器是否能生成 32/64位代码

mingw-w64提供的编译器不同的版本生成代码的能力是不一样的,有的只能生成32位代码 有的只能生成64位代码,在powershell脚本中,为了自动化执行编...

17110
来自专栏用户画像

shell脚本 >/dev/null 2>&1

1:> 代表重定向到哪里,例如:echo "123" > /home/123.txt

561
来自专栏Python小屋

把Python程序的输出和异常信息自动写入文件

一般情况下,Python的内置函数print()会把数据输出到标准控制台,也就是屏幕,当然这可以通过为print()函数传递file参数来改变。如果代码执行过程...

571
来自专栏CaiRui

Python 文件和异常

一、从文件中读取数据 #!/usr/bin/env python with open('pi') as file_object: contents =...

19510
来自专栏非著名程序员

Android Studio下的JNI开发(二):C/C++代码编写与编译

前一篇简单介绍了Android Studio环境下NDK的配置,本篇将通过一个简单的例子,介绍Android Studio中C/C++代码的编写与编译。 下面我...

1725

扫码关注云+社区