手动实现.*正则表达式匹配函数

muddyway 发布于2019-07-25 12:02 / 1037人阅读

摘要：手动实现正则表达式匹配函数思路使用迭代，当每次判断后令当时特殊处理，注意可以代表到多个之前一个的字符当时，循环判断代表多少个之前一个的字符，如果可以匹配之后的模式，返回，否则注意处理边界值的情况，和为空串时代码可以代表一到多次本题以及其它题

手动实现.*正则表达式匹配函数 regular expression matching

"." Matches any single character.

"*" Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Some examples:

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
isMatch("bbbba", ".*a*a") → true
isMatch("a", ".*..a*") → False
isMatch("a", "ab*") → true 
isMatch("ab", ".*c") → False

思路

使用迭代，当p[1] != "*"每次判断p[0] == s[0]后令s = s[1:], p = p[1:]

当p[1] == "*"时特殊处理，注意 * 可以代表0到多个*之前一个的字符

当p[1] == "*"时，循环判断*代表多少个*之前一个的字符，如果s可以匹配*之后的模式，返回True，否则s = s[1:]

注意处理边界值的情况，s 和 p为空串时

代码

class Solution(object):
    def matchChar(self, sc, pc):
        return sc == pc or pc == "."

    def isEndOfStar(self, p):
        while p != "":
            if len(p) == 1 or len(p) > 1 and p[1] != "*":
                return False
            p = p[2:]
        return True

    def isMatch(self, s, p):
        if p == "":
            return s == ""

        if s == "":
            return self.isEndOfStar(p)

        if (len(p) > 1 and p[1] != "*") or len(p) == 1:
            # without *
            if not self.matchChar(s[0], p[0]):
                return False
            else:
                return self.isMatch(s[1:], p[1:])

        else:
            # with *
            # try see x* is empty
            if self.isMatch(s[0:], p[2:]):
                return True

            # x* 可以 代表 x 一到多次
            while self.matchChar(s[0], p[0]):
                s = s[1:]

                if self.isMatch(s, p[2:]):
                    return True

                if s == "":
                    return self.isEndOfStar(p)
            return False

本题以及其它leetcode题目代码github地址: github地址

GPU云服务器云服务器正则匹配正则表达式正则表达式匹配匹配php正则表达式 js正则表达匹配

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38649.html

JavaScript正则表达式的匹配模式

摘要：选择分组和引用正则表达式的语法还包括指定选择项子表达式分组和引用前一子表达式的特殊字符。带圆括号的表达式的另一个用途是允许在同一正则表达式的后部引用前面的子表达式。正则表达式(regular expression)是一个描述字符模式的对象。JavaScript的 RegExp类表示正则表达式，String和RegExp都定义了方法，后者使用正则表达式进行强大的模式匹配和文本检索与...

wqj97 2019-08-20 18:56 评论0 收藏0
正则表达式入门实践（一）

摘要：一前言正则表达式入门实践系列文章适合熟悉至少使用过正则表达式的同学，在文章开始的时候我们都会带着问题去思考如何正确应用正则表达式解决出现的问题，在解决问题的过程中增长你的知识，提高你的实践能力。一前言正则表达式入门实践系列文章适合熟悉至少使用过正则表达式的同学，在文章开始的时候我们都会带着问题去思考如何正确应用正则表达式解决出现的问题，在解决问题的过程中增长你的知识，提高你的实践...

chanthuang 2019-08-22 13:45 评论0 收藏0
正则基础详解

摘要：正则基础详解开头，结尾匹配次或多次匹配次匹配次或次当跟在后面时，匹配模式是非贪婪的匹配确定是次，非负数匹配除了换行符以外的任何字符包括点本身小括号中的内容只匹配不捕获正向预查负向预查匹配或者匹配中任何一个匹配未包含的任意字符匹配指定范围正则基础详解 /^开头，结尾$/ * 匹配0次或多次 + 匹配1-n次？匹配0次或1次；当?跟在 * + {n} {n,m} {n,} 后面时...

YanceyOfficial 2019-08-26 11:37 评论0 收藏0
python爬虫抓取纯静态网站及其资源

摘要：下面跟大家详细分享一下写爬虫抓取静态网站的全过程。而我们上面说的元字符都代表一定的规则和占据一定的字符。遇到的需求前段时间需要快速做个静态展示页面，要求是响应式和较美观。由于时间较短，自己动手写的话也有点麻烦，所以就打算上网找现成的。中途找到了几个页面发现不错，然后就开始思考怎么把页面给下载下来。由于之前还没有了解过爬虫，自然也就没有想到可以用爬虫来抓取网页内容。所以我采取的办...

daydream 2019-07-30 17:16 评论0 收藏0
正则与JS中的正则

摘要：注意本文将正则与中的正则分开讨论。正则零宽断言更多参考各种语言对于正则不同支持参考单行模式与多行模式通过设置正则表达式后的修饰符可开启对应的匹配模式单行模式和多行模式。最近这段时间帮同学处理一些文档，涉及到一些结构化文档的工作大部分都得使用正则表达式，之前对于正则的认识大多来源于语言书上那几页的介绍，自己也没有用过几次。这里将我之前感到模糊的概念作个整理。因为对JS了解多点，所...

firim 2019-08-19 17:11 评论0 收藏0