摘要：实现支持和的正则表达式匹配。匹配任意单个字符。匹配零个或多个前面的元素。匹配应该覆盖整个字符串，而不是部分字符串。不过查别人效率比我高的提交中，很多人用的是库中的匹配函数，心里略微平衡了一点把别人提交的效率最高的代码贴出来执行只用
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
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/42748.html
摘要：选择分组和引用正则表达式的语法还包括指定选择项子表达式分组和引用前一子表达式的特殊字符。带圆括号的表达式的另一个用途是允许在同一正则表达式的后部引用前面的子表达式。 正则表达式(regular expression)是一个描述字符模式的对象。JavaScript的 RegExp类 表示正则表达式，String和RegExp都定义了方法，后者使用正则表达式进 行强大的模式匹配和文本检索与...
摘要：控制权和传动这两个词可能在搜一些博文或者资料的时候会遇到，这里做一个解释先控制权是指哪一个正则子表达式可能为一个普通字符元字符或元字符序列组成在匹配字符串，那么控制权就在哪。 温馨提示：文章很长很长，保持耐心，必要时可以跳着看，当然用来查也是不错的。 正则啊，就像一座灯塔，当你在字符串的海洋不知所措的时候，总能给你一点思路；正则啊，就像一台验钞机，在你不知道用户提交的钞票真假的时候，...
摘要：正则表达式一直是里比较难以掌握的点。在中创建正则的两种方式使用字面量这就是正则表达式的字面量语法，表示正则表达式的模式，为正则表达式的标志。字面量形式的正则表达式一般使用较多，也推荐大家尽可能使用这种形式，简洁易读，符合正常的使用习惯。 正则表达式一直是js里比较难以掌握的点。 看不懂，学不会，记不住。 每次需要用到正则的时候，都需要再去查找资料。 今天花时间把正则的知识点总结下，希望...
摘要：正则表达式的意义中的正则表达式使用表示，可以使用构造函数来创建对象，不过对象更多的是通过一种特殊的直接量语法来创建。用构造函数也可以定义一个与之等价的正则表达式，代码如下正则表达式的模式规则是由一个字符序列组成的。 正则表达式的模式匹配 正则表达式(regular expression)是一个描述字符模式的对象。javascript的RegExp对象表示正则表达式，String和Reg...
摘要：引用就是允许在同一个正则表达式的后部引用前面的子表达式。这个数字制定了带圆括号的子表达式在正则表达式中的位置。对正则表达式中前一个子表达式的引用，并不是指对子表达式模式的引用，而是指与那个模式匹配的文本的引用。 前言 本文主要是在读《JavaScript高级程序语言设计》一书有关正则表达式的章节的知识点记录，方便后续查阅。 什么是正则表达式 正则表达式是用来描述字符组合的某种规则。它可...
阅读 2758·2023-04-25 23:08
阅读 1538·2021-11-23 09:51
阅读 1529·2021-10-27 14:18
阅读 3090·2019-08-29 13:25
阅读 2790·2019-08-29 13:14
阅读 2807·2019-08-26 18:36
阅读 2171·2019-08-26 12:11
阅读 776·2019-08-26 11:29
