正则表达式匹配

Charles 发布于2019-07-30 18:37 / 1886人阅读

摘要：实现支持和的正则表达式匹配。匹配任意单个字符。匹配零个或多个前面的元素。匹配应该覆盖整个字符串，而不是部分字符串。不过查别人效率比我高的提交中，很多人用的是库中的匹配函数，心里略微平衡了一点把别人提交的效率最高的代码贴出来执行只用

leetcode上面的题目解题及重构
题干：给定一个字符串 (s) 和一个字符模式 (p)。实现支持 "." 和 "*" 的正则表达式匹配。

 "." 匹配任意单个字符。 
 "*" 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
题目及示例传送门

如果直接用re，那这题就没意义了，所以肯定要自己写匹配算法
第一次成功提交代码：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        if len(p) == 1:
            return len(s) == 1 and (s == p or p == ".")
        if p[1] != "*":
            if s == "":
                return False
            return (p[0] == s[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])
        while s and (p[0] == s[0] or p[0] == "."):
            if self.isMatch(s, p[2:]):
                return True
            s = s[1:]
        return self.isMatch(s, p[2:])

执行用时：1100 ms，执行效率算很差，只超过了32%的提交效率
优化后第二次提交：

def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        if len(p) == 1:
            return False if len(s) != 1 else (s == p or p == "." or p == "*")
        if (p[-1] != "*") and (p[-1] != ".") and (p[-1] not in s): 
            return False 
        if (p[1] != "*"): 
            return s != "" and (p[0] == s[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])
        else:
            while s and (p[0] == s[0] or p[0] == "."):
                if self.isMatch(s, p[2:]):
                    return True
                s = s[1:]
            return self.isMatch(s, p[2:])

执行用时间优化到140 ms，但也只超过了40%的提交效率。
不过查别人效率比我高的提交中，很多人用的是re库中的匹配函数，心里略微平衡了一点

把别人提交的效率最高的代码贴出来：

class Solution(object):
    def isMatch(self, s, p, memo={("",""):True}):
        if not p and s:      return False
        if not s and p:      return set(p[1::2]) == {"*"} and not (len(p) % 2)
        if (s,p) in memo:    return memo[s,p]

        char, exp, prev = s[-1], p[-1], 0 if len(p) < 2 else p[-2]
        memo[s,p] =
               (exp == "*" and ((prev in {char, "."} and self.isMatch(s[:-1], p, memo)) or self.isMatch(s, p[:-2], memo)))
               or
               (exp in {char, "."} and self.isMatch(s[:-1], p[:-1], memo))
        return memo[s,p]

执行只用36ms

混合云专线服务正则匹配正则表达式正则表达式匹配匹配php正则表达式 js正则表达匹配

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

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

JavaScript正则表达式的匹配模式

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

wqj97 2019-08-20 18:56 评论0 收藏0
JavaScript正则表达式总结

摘要：正则表达式一直是里比较难以掌握的点。在中创建正则的两种方式使用字面量这就是正则表达式的字面量语法，表示正则表达式的模式，为正则表达式的标志。字面量形式的正则表达式一般使用较多，也推荐大家尽可能使用这种形式，简洁易读，符合正常的使用习惯。正则表达式一直是js里比较难以掌握的点。看不懂，学不会，记不住。每次需要用到正则的时候，都需要再去查找资料。今天花时间把正则的知识点总结下，希望...

big_cat 2019-08-22 18:32 评论0 收藏0
JS正则表达式一条龙讲解，从原理和语法到JS正则、ES6正则扩展，最后再到正则实践思路

摘要：控制权和传动这两个词可能在搜一些博文或者资料的时候会遇到，这里做一个解释先控制权是指哪一个正则子表达式可能为一个普通字符元字符或元字符序列组成在匹配字符串，那么控制权就在哪。温馨提示：文章很长很长，保持耐心，必要时可以跳着看，当然用来查也是不错的。正则啊，就像一座灯塔，当你在字符串的海洋不知所措的时候，总能给你一点思路；正则啊，就像一台验钞机，在你不知道用户提交的钞票真假的时候，...

Michael_Lin 2019-08-20 13:39 评论0 收藏0
JavaScript 中的正则表达式

摘要：正则表达式的意义中的正则表达式使用表示，可以使用构造函数来创建对象，不过对象更多的是通过一种特殊的直接量语法来创建。用构造函数也可以定义一个与之等价的正则表达式，代码如下正则表达式的模式规则是由一个字符序列组成的。正则表达式的模式匹配正则表达式(regular expression)是一个描述字符模式的对象。javascript的RegExp对象表示正则表达式，String和Reg...

_Dreams 2019-08-19 18:40 评论0 收藏0
JavaScript正则表达式

摘要：引用就是允许在同一个正则表达式的后部引用前面的子表达式。这个数字制定了带圆括号的子表达式在正则表达式中的位置。对正则表达式中前一个子表达式的引用，并不是指对子表达式模式的引用，而是指与那个模式匹配的文本的引用。前言本文主要是在读《JavaScript高级程序语言设计》一书有关正则表达式的章节的知识点记录，方便后续查阅。什么是正则表达式正则表达式是用来描述字符组合的某种规则。它可...

sixleaves 2019-08-21 11:17 评论0 收藏0
正则与JS中的正则

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

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