文档章节

LeetCode 10. 正则表达式匹配 | Python

o
 osc_ym1l2qni
发布于 05/03 09:56
字数 1486
阅读 72
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

10. 正则表达式匹配


题目来源:https://leetcode-cn.com/problems/regular-expression-matching

题目


给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

解题思路


暴力解

先从【暴力解】的角度理清问题。

这个题目中,难点就在于处理 .* 两个符号。

如果只是要求检查两个普通字符是否匹配。那么通过直接遍历,检查每个数组对应的元素是否相同来判断是否匹配即可。例如:

def isMatch(s, p):
    if len(s) != len(p):
        return False
    for i in range(p):
        if s[i] != p[i]:
            return False
    return True

那代码大概就会是这样。那我们用递归的形式来书写,以下为伪代码:

def isMatch(s, p):
    """
    s: text
    p: pattern
    """
    if p is empty:
        return s is empty
    first_match = (s not empty) and p[0] == s[0]
    return first_match and isMatch(s[1:], p[1:])

在上面的代码中,其实就是通过先判断前面的元素是否匹配,逐层往下判断后面的元素是否也匹配,从而来找到答案。

现在来处理两个符号的问题,. 这个符号,表示的是匹配处换行符以外的任意字符(这里就不展开说明了,若需详细了解,可直接上网搜索)。

了解这个符号的含义后,这里所能表达的意义,也会相应的改变,即是说,当 p 中出现 . 号,s 对应的元素无论是什么字符(题目说明 s 仅包含 a-z 字符)都能够匹配,现在根据上面的伪代码进行修改:

def isMatch(s, p):
    """
    s: text
    p: pattern
    """
    if not p:
        return not s
    first_match = bool(s) and p[0] in {s[0], '.'}
    return first_match and isMatch(s[1:], p[1:])

这里唯一不同的就是 first_match 这部分的判断中,因为 p 中的元素可能出现固定字符,或者 . 号,所以当 p 出现的字符与 s 中对应的字符相同,或者 p 此处是 . 字符,这里两者都表示能够匹配。

那么现在往下看 * 符号,这个符号表示的含义是重复零次或多次。那么这里最明显的字符就是重复多少次的问题?在这里考虑使用递归的方式书写,假设重复 n 次,其实这里先不需要考虑 n 是多少,把这个交给递归实现。要考虑那么当下的情况,这里应该就只有两个选择,要么是匹配 0 次,要么是匹配 1 次。

那么相应的代码就应该修改为(这里书写发现 * 的情况):

# 这里表示发现 `*` 的情况下,
if len(p) >= 2 and p[1] == '*':
    # 这里需要考虑匹配 0 次的问题,例如 aa,c*aa
    # 也要考虑匹配多次的问题,例如 aa, a*
    return isMatch(s, p[2:]) or first_match and isMatch(s[1:], p)

在这段代码当中,isMatch(s, p[2:]) 这里表示,字符匹配 0 次,跳过 p 中字符与 * 结合这部分。后面的表示,p[0] 和 s[0] 匹配之后,继续判断 s 接下来的元素。其中保留 p,只向后移动 s,是为了实现 * 匹配多次的功能。

这样来看,其实已经可以说理清两个符号的具体实现方式。

关于完整的代码请查看【代码实现】部分。

动态规划

思路:动态规划

在上面暴力解的方法中,频繁使用切片操作,复杂度高。这里在暴力解的基础上,使用动态规划的方法,定义变量 i,j 来记录当前匹配到的位置,用 dp(i, j) 表示 s[i:] 和 p[j:] 是否能够匹配。,避免频繁切片。这里也引入备忘录的概念,用来避免重复的运算。

具体代码同样请查看【代码实现】部分。

代码实现


暴力解 | 代码实现
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p:
            return not s

        first_match = bool(s) and p[0] in {s[0], '.'}

        if len(p) >= 2 and p[1]=="*":
            return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
        else:
            return first_match and self.isMatch(s[1:], p[1:])
动态规划 | 代码实现
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(p):
                    return i == len(s)

                else:
                    first_match = i < len(s) and p[j] in {s[i], '.'}
                    if j + 1 < len(p) and p[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[(i, j)] = ans

            return memo[(i, j)]

        return dp(0, 0)


实现结果


暴力解 | 实现结果

暴力解 | 实现结果

动态规划 | 实现结果

动态规划 | 实现结果


以上就是使用暴力解的形式,理清题目的难点,进而使用动态规划加备忘录的形式来进一步降低复杂度,更高效的解决《10. 正则表达式匹配》问题的主要内容。


欢迎关注微信公众号《书所集录》

o
粉丝 0
博文 62
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
DNS服务器软件--BIND 10

BIND 10 是下一代的 Bind 。 Bind是一款开放源码的DNS服务器软件,Bind由美国加州大学Berkeley分校开发和维护的,全名为Berkeley Internet Name Domain它是目前世界上使用最为广泛的DNS服务器...

匿名
2013/02/22
3.7K
1
Swing界面分析和调试工具--Swing Inspector

Swing Inspector是一个Java Swing/AWT用户界面分析和调试工具,功能与firebug类似,具有强大的Swing/AWT用户界面分析和调试相关功能。 适用于从java swing初级到高级的所有开发人员,能够快速...

匿名
2013/03/06
3.3K
0
开源数据访问组件--Smark.Data

Smark.Data是基于Ado.net实现的数据访问组件,提供基于强类型的查询表达式进行灵活的数据查询,统计,修改和删除等操作;采用基于条件驱动的操作模式,使数据操作更简单轻松;内部通过标准SQL...

泥水佬
2013/03/12
2.5K
0
django-c10k-demo

这是一个演示程序,用来实现同时 10000 个并发连接到 Django 。涉及的概念包括:the C10k problem, the WebSocket protocol, the Django web framework, and Python's upcoming asynchronou......

匿名
2013/03/27
1.7K
0
Java™ 编译器--Janino

Janino是一个超级小但又超级快的Java™ 编译器. 它不仅能像javac工具那样讲一组源文件编译成字节码文件,还可以对一些Java表达式,代码块,类中的文本(class body)或者内存中源文件进行编译,...

匿名
2013/04/02
4.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

认识Node

什么是Node? Node 是 JavaScript 的一种运行环境。可以使 JS 代码不依赖浏览器也可以执行。他俩的差异如下: 两个运行环境都包含了 ECMScript 。另一方面 JavaScript 包含了 BOM 和 DOM。 ...

长臂猿猴
10分钟前
13
0
正则表达式中的非捕获组是什么? - What is a non-capturing group in regular expressions?

问题: 非捕获组(即(?:) )如何在正则表达式中使用,它们有什么用? 解决方案: 参考一: https://stackoom.com/question/Ejkl/正则表达式中的非捕获组是什么 参考二: https://oldbug.net...

技术盛宴
10分钟前
6
0
他在国外演讲时说,学Python只要看答案做完这几十道题,就足够了

你想学Python?其实很简单,因为Python本身就是一门比较简单的编程语言。 你要做的也就是看着答案做完这几十道题就可以了,不管你是不是有编程基础,因为答案摆在那儿,你不可能不会做。 为什...

python小天
10分钟前
0
0
「2020最新」Spring最易学习教程 4—整合Mybatis 事务控制

0 复习 代理模式 代理模式,可以为目标类添加额外功能。 Spring 动态代理 定义目标类对象 定义额外功能,增强。实现Spring内置的接口 配置增强类 定义切入点 编织组装 增强类型 前置增强 Me...

鹿老师的Java笔记
30分钟前
21
0
OpenCV开发笔记(六十九):红胖子8分钟带你使用传统方法识别已知物体(图文并茂+浅显易懂+程序源码)

若该文为原创文章,未经允许不得转载 原博主博客地址:https://blog.csdn.net/qq21497936 原博主博客导航:https://blog.csdn.net/qq21497936/article/details/102478062 本文章博客地址:h...

红模仿_红胖子
47分钟前
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部