专栏首页用户6811391的专栏LeetCode 刷题笔记 #10 正则表达式匹配

LeetCode 刷题笔记 #10 正则表达式匹配

昨天有提到今天这题是困难级别的,琢磨半天目前只弄了个耗时很久勉强完成任务的版本,明天再继续研究优化。

题目

中文题目

第 10 题 正则表达式匹配:

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

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素

所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

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

示例:

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

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

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/regular-expression-matching

说白了,就是让我们来设计实现正则表达式里的 "." 和 "*" 的逻辑。

思路

因为 "*" 可以匹配零个或多个前面的元素,也就是会改变 p 字符串长度的。那反过来想,如果 p 中没有星号,这就很简单了,p 和 s 等长,只要看对应位置上 p 中的字符要么为 "." 要么与 s 中字符相同,如果全符合,返回 True,否则 False。

接下来复杂些的是 p 中有 "*",那既然有星号,那它最早也是出现在第二位也就是 p[1] 位置,出现在 p[0] 是没有意义的。如果它没出现在 p[1], 且 s[0] 和 p[0] 相同的话,那么我们可以把 p 和 s 的第一位同时删去来重新检测。也就是检测完第一位相同且 p[1] 不是星号,那么就可以调用 isMatch(s[1:],p[1:]) 来继续检测剩余子串。

但是如果 "*" 出现在了第二位:要么星号发挥的是 0 个之前字符的作用,这时就可以把 p 的前两位拿走重新与 s 来检测;要么星号是复制的前面那个字符,这时就可以把 s 的第一个字符拿走,用完整的 p 来继续检测 s[1:] 了。如果以上这两个条件可以一直达标且结果为 True,那么结果就是 True 了。

这里的主要思路就是在函数中删去前几位来继续调用 isMatch() 来对剩余子串进行检测。

代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # p 中有 * 的情况
        if "*" in p:     
            # 检测 s 非空 且 p 首位要么与 s 相同、要么为 .       
            temp =  s and p[0] in [".",s[0]]
            # 对应思路中的 p[1] 为 *
            if len(p)>1 and p[1]=="*":                           
                return self.isMatch(s,p[2:]) or (temp and self.isMatch(s[1:],p))
            # 对应 p[1] 不为 *
            else:
                return temp and self.isMatch(s[1:],p[1:])
        # p 为空
        elif p=="":
            if s=="":
                return True
            else:
                return False
        # p非空,且不含 *
        else:
            if len(p)!=len(s):
                return False
            try:
                for i,c in enumerate(p):
                    if c!="." and c!=s[i]:
                        print(c,s[i])
                        return False
                return True
            except:
                return False  

提交答案

这次提交答案,只追求能通过测试。

中文区结果:

解答错误 问题出在 s="ab" p=".*c" 上

英文版结果:

Runtime: 3152 ms, faster than 5.04% of Python3 online submissions for Regular Expression Matching. Memory Usage: 14 MB, less than 5.55% of Python3 online submissions for Regular Expression Matching.

这就有些奇怪了。。

结论

第十题,困难难度,勉强通过,还在研究,希望明天可以完成吧。

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 模拟除法与匹配单词—— LeetCode 第 29、30 题记

    今天遇到的是一道不用除号来实现除法运算的中等难度的题,和一道在字符串中检测匹配特定词语的困难级别的题。然而中等难度的,花费两个多小时才完成,困难的这道半个多小时...

    TTTEED
  • 猜音谜——倒放音频挑战赛

    前两天刷哔哩哔哩,看了两期《小翔哥是世界上最帅的男人》和《笑死人的倒放挑战》视频,视频里他们将语音或者音频倒着播放,特别搞笑。

    TTTEED
  • Python 刷题笔记:二叉树专题二

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

    TTTEED
  • 抛出和接收异常的顺序

    异常(exception)是C++语言引入的错误处理机制。它 采用了统一的方式对程序的运行时错误进行处理,具有标准化、安全和高效的特点。C++为了实现异常处理,...

    Dabelv
  • C++抛出和接收异常的顺序

    异常(exception)是C++语言引入的错误处理机制。它 采用了统一的方式对程序的运行时错误进行处理,具有标准化、安全和高效的特点。C++为了实现异常处理,...

    Dabelv
  • 学python是自学好还是去培训机构?这个问题应该这样分析

    因为目前python非常火,应用非常的广泛,是目前最火的行业之一,竞争很大,工资很高,未来发展也极好。

    python学习教程
  • vue-qr二维码插件使用简介

    官方介绍:https://www.npmjs.com/package/vue-qr

    kirin
  • 央行官员再次表态:强化对各类虚拟货币的监测监管!

    4月10日,央行货币金银局局长王信发表署名文章《切实加强虚拟货币监管 牢牢维护国家货币发行权》。文章提到,近年来,各类虚拟货币在全世界引发高度关注,它们吸纳民间...

    区块链领域
  • ffmpeg编译安装过程报错解决

    版权声明:本文为木偶人shaon原创文章,转载请注明原文地址,非常感谢。 https://b...

    shaonbean
  • React + Dva + Antd+umi 实践

    记录一下最近项目所用到的技术React + Dva + Antd + umi ,以免忘记。之前没有用过它们其中一个,也是慢慢摸索,了解数据整个流程。

    特立独行的猫a

扫码关注云+社区

领取腾讯云代金券