正则表达式匹配

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

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

二项队列

二项队列是 堆序 的集合,也叫 森林。其中每一种形式都有约束。 二项树Bk由一个带有儿子的B0,B1,B2...组成,高度为k的二项树 恰好有2^k个结点。每一...

2725
来自专栏刘晓杰

Glide缓存机制

34711
来自专栏技术小黑屋

研究学习Kotlin的一些方法

Kotlin是一门让人感到很舒服的语言,相比Java来说,它更加简洁,省去了琐琐碎碎的语法工作,同时了提供了类似Lambda,String template,N...

701
来自专栏海天一树

TopCoder SRM 731 Div2 Easy题解报告

Problem Statement Hero has an infinite periodic string t. You are given the stri...

2296
来自专栏专知

关关的刷题日记76 – Leetcode 234. Palindrome Linked List

关关的刷题日记76 – Leetcode 234. Palindrome Linked List 题目 Given a singly linked list, ...

3159
来自专栏冰霜之地

深入研究Block用weakSelf、strongSelf、@weakify、@strongify解决循环引用

在上篇中,仔细分析了一下Block的实现原理以及__block捕获外部变量的原理。然而实际使用Block过程中,还是会遇到一些问题,比如Retain Circl...

961
来自专栏mathor

回文自动机、AC自动机和后缀自动机介绍(2)

 AC自动机,有的地方也叫Trie图,可以用来解决多串匹配的问题  多串匹配是这样一个问题:给定N个敏感词W1, W2, W3, … WN,然后对于一个字符串...

2262
来自专栏青玉伏案

算法导论之最大子段和

  《算法导论》一书中对最大字段和可谓讲的是栩栩如生,楚楚动人。如果简单的说最大字段和,没有意义。而《算法导论》上举了一个股票的例子。根据股票每天结束的价格来求...

2027
来自专栏Java架构师历程

jsoup解析的常见用法

1、解析attribute中值,如下面所示的serviceID和serviceName:

1243
来自专栏SeanCheney的专栏

《Pandas Cookbook》第07章 分组聚合、过滤、转换1. 定义聚合2. 用多个列和函数进行分组和聚合3. 分组后去除多级索引4. 自定义聚合函数5. 用 *args 和 **kwargs

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

762

扫码关注云+社区