当前位置:首页 » 《随便一记》 » 正文

【Leetcode刷题】10. 正则表达式匹配_202xxx的博客

17 人参与  2021年11月19日 17:43  分类 : 《随便一记》  评论

点击全文阅读


题目

描述

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

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

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

示例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

提示

(1)0 <= s.length <= 20
(2)0 <= p.length <= 30
(3)s 可能为空,且只包含从 a-z 的小写字母。
(4)p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
(5)保证每次出现字符 * 时,前面都匹配到有效的字符

解题思路

(1)使用动态规划对字符串进行匹配

(2)创建(m+1)行(n+1)列的dp矩阵f

(3)以s = "mississippi" p = "mis*is*p*."为例,创建11行11列的dp矩阵f

""mmimismis*mis*imis*ismis*is*mis*is*pmis*is*p*mis*is*p*.
“”TFFFFFFFFFF
mFTFFFFFFFFF
miFFTFTFFFFFF
misFFFTTFFFFFF
missFFFFTFFFFFF
missiFFFFFTFTFFF
missisFFFFFFTTFTF
mississFFFFFFFTFTT
mississiFFFFFFFFFTT
mississipFFFFFFFFFFT
mississippFFFFFFFFFFF
mississippiFFFFFFFFFFF

(4)如果最新字符为“.”,用match函数来匹配前一个字符,如果行列的两个字符相等,那只需要考虑没有增加新的字符时的结果,相等的话,那新增之后也相等

if matches(i, j):
    f[i][j] = f[i - 1][j - 1]

def matches(i: int, j: int) -> bool:
    if p[j - 1] == '.':
        return True

(5)如果新增字符为“*”,则考虑“*”的四种状态,0个,1个,2个,多个字符(多个不考虑,因为多个是由多个2个组成,可以在i+1中体现)

(6)0个前面字符时相当与删除了两个字符,前面字符和“*”

例子:mis*与miss对比,如果是0个字符时,则为mi与miss对比

f[i][j] = f[i][j - 2]

(7)1个前面字符时用match函数判断新增字符与前一个字符是否相等

例子:mis*与miss对比,如果是1个字符时,则为mis与miss对比

f[i][j] = f[i - 1][j]

(7)2个前面字符时用match函数判断没有添加两个新增字符时是否相等

例子:mis*与miss对比,如果是2个字符时,则为miss与miss对比,match函数判断mis与mis是否相等

if matches(i, j):
    f[i][j] = f[i - 1][j - 1]

def matches(i: int, j: int) -> bool:
    return s[i - 1] == p[j - 1]

(8)最后输出f[m][n]

(9)对于动态规划的一些思考:每次以最新一行为基础,根据问题背景考虑复用前一行或者多行的最优结果,作为本行的最优进行填充,如果需要考虑到计算,则以考虑本行的最优和不考虑本行的最优择取最优。

代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        def matches(i: int, j: int) -> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]

        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] = f[i][j - 2]
                    if matches(i, j - 1):
                        f[i][j] = f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] = f[i - 1][j - 1]
        return f[m][n]

Reference

题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/31043.html

字符  多个  匹配  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1