文档章节

正则表达式匹配

G
 Garphy
发布于 09/15 12:55
字数 1264
阅读 10
收藏 0

请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。模式中的字符 '.' 表示任意一个字符,而 '*' 表示它前面的字符可以出现任意次(包含 0 次)。

在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配,但是与 "aa.a" 和 "ab*a" 均不匹配。

 

应该注意到,'.' 是用来当做一个任意字符,而 '*' 是用来重复前面的字符。这两个的作用不同,不能把 '.' 的作用和 '*' 进行类比,从而把它当成重复前面字符一次。

 


/*
    解这题需要把题意仔细研究清楚,反正我试了好多次才明白的。
    首先,考虑特殊情况:
         1>两个字符串都为空,返回true
         2>当第一个字符串不空,而第二个字符串空了,返回false(因为这样,就无法
            匹配成功了,而如果第一个字符串空了,第二个字符串非空,还是可能匹配成
            功的,比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次,
            所以有可能匹配成功)
    之后就开始匹配第一个字符,这里有两种可能:匹配成功或匹配失败。但考虑到pattern
    下一个字符可能是‘*’, 这里我们分两种情况讨论:pattern下一个字符为‘*’或
    不为‘*’:
          1>pattern下一个字符不为‘*’:这种情况比较简单,直接匹配当前字符。如果
            匹配成功,继续匹配下一个;如果匹配失败,直接返回false。注意这里的
            “匹配成功”,除了两个字符相同的情况外,还有一种情况,就是pattern的
            当前字符为‘.’,同时str的当前字符不为‘\0’。
          2>pattern下一个字符为‘*’时,稍微复杂一些,因为‘*’可以代表0个或多个。
            这里把这些情况都考虑到:
               a>当‘*’匹配0个字符时,str当前字符不变,pattern当前字符后移两位,
                跳过这个‘*’符号;
               b>当‘*’匹配1个或多个时,str当前字符移向下一个,pattern当前字符
                不变。(这里匹配1个或多个可以看成一种情况,因为:当匹配一个时,
                由于str移到了下一个字符,而pattern字符不变,就回到了上边的情况a;
                当匹配多于一个字符时,相当于从str的下一个字符继续开始匹配)
    之后再写代码就很简单了。
*/

链接:https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c?f=discussion
来源:牛客网
 

当模式中的第二个字符不是“*”时:

1、如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。

2、如果 字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。

 

而当模式中的第二个字符是“*”时:

如果字符串第一个字符跟模式第一个字符不匹配,则模式后移2个字符,继续匹配。如果字符串第一个字符跟模式第一个字符匹配,可以有3种匹配方式:

1、模式后移2字符,相当于x*被忽略;

2、字符串后移1字符,模式后移2字符;

3、字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位;

 

这里需要注意的是:Java里,要时刻检验数组是否越界。

链接:https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c?f=discussion
来源:牛客网

public class Solution {
    public boolean match(char[] str, char[] pattern) {
    if (str == null || pattern == null) {
        return false;
    }
    int strIndex = 0;
    int patternIndex = 0;
    return matchCore(str, strIndex, pattern, patternIndex);
}
  
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
    //有效性检验:str到尾,pattern到尾,匹配成功
    if (strIndex == str.length && patternIndex == pattern.length) {
        return true;
    }
    //pattern先到尾,匹配失败
    if (strIndex != str.length && patternIndex == pattern.length) {
        return false;
    }
    //模式第2个是*,且字符串第1个跟模式第1个匹配,分3种匹配模式;如不匹配,模式后移2位
    if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2,视为x*匹配0个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个,再匹配str中的下一个
        } else {
            return matchCore(str, strIndex, pattern, patternIndex + 2);
        }
    }
    //模式第2个不是*,且字符串第1个跟模式第1个匹配,则都后移1位,否则直接返回false
    if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
        return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
    }
    return false;
    }
}

 

© 著作权归作者所有

下一篇: 构建乘积数组
G
粉丝 1
博文 160
码字总数 69435
作品 0
私信 提问
正则表达式-正则表达式的创建

正则表达式就是一个字符模式。和String对象类似,在JavaScript中正则表达式也是一个对象,它主要用于字符串的模式匹配。创建正则表达式有两种方式:隐式创建(文字量方法)和显示创建(使用构...

oQo先生
2017/03/27
0
0
Python全栈 正则表达式(概念、、语法、元字符、re模块)

前言: 普通人有三件东西看不懂:医生的处方,道士的鬼符,程序员得正则表达式 什么是正则表达式? 正则表达式,又称规则表达式,英文名为Regular Expression,在代码中常简写为regex、regex...

巴黎香榭
2018/08/24
0
0
JS中与正则有关的方法

最近正在拜读老姚的《JavaScript 正则表达式迷你书》,碰巧项目中也会时不时的用到正则,所以今天来总结一下JS中有关正则的方法。 RegExp对象方法 字符串的方法,比较常用在判断语句中,最简...

坤少卡卡
2017/12/15
0
0
007零基础学Python:Python 正则表达式--学习笔记

Python 正则表达式 正则表达式基础 基本概念: 执行原理: 基本语法: 模式 描述 ^ 匹配字符串的开头 $ 匹配字符串的末尾。 . 匹配任意字符,除了换行符,当re.DOTALL标记被指定时,则可以匹...

weir_will
2017/07/02
0
0
Java正则系列: (1)入门教程

本文简要介绍Java的正则表达式及其实现方式,并通过实例讲解正则表达式的具体用法。 1. 正则表达式 1.1. 简介 正则表达式(Regular Expression), 简称 正则, 也翻译为 正规式, 用来表示文本搜...

renfufei
2018/01/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

常用正则表达式整理

本文转载于:专业的前端网站➩常用正则表达式整理 /*以下为亲自验证过,备用*/   数字,0-100,包含0和100,且小数点后最多有三位: /^(\d{1,2}(\.\d{1,3})?|100)$/ 匹配正整数:^[1-9]*[1-9][...

前端老手
5分钟前
0
0
Java 中可重入锁、不可重入锁的测试

Java 中可重入锁、不可重入锁的测试 可重入锁 指在同一个线程在外层方法获取锁的时候,进入内层方法会自动获取锁。 为了避免死锁的发生,JDK 中基本都是可重入锁。 下面我们来测试一下 sync...

ConstXiong
5分钟前
0
0
怎么给视频变音

怎么让录制视频中的声音变得可爱吗?其实方法非常的简单,只要进行视频变音制作就好了,那怎么给视频变音呢?下面就一起来看看视频变音的具体制作方法吧! 具体步骤如下: 第一步: 打开手机...

白米稀饭2019
9分钟前
2
0
学习记录(ECMAScript 6.0入门_day01重点总结)

课程目标 1、ECMAScript6和JAVAScript关系 ES6是JAVAScript的规格,JavaScript是ES6的一种实现。 变量声明: 局部变量:let 它的用法类似于var,但是所声明的变量,只在let命令所在的代码块内...

庭前云落
21分钟前
2
0
springboot 源码SpringApplication的run方法解析

public ConfigurableApplicationContext run(String... args) {//记录启动应用启动时间StopWatch stopWatch = new StopWatch();stopWatch.start();ConfigurableApplicationCo......

dudu
23分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部