leetCode第十题 : 正则表达式匹配 动态规划【10/1000 python】

简介: leetCode第十题 : 正则表达式匹配 动态规划【10/1000 python】

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

image.png

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给你一个字符串 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

解释:".*" 表示可匹配零个或多个('*')任意字符('.')。



提示:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母,以及字符 .*
  • 保证每次出现字符 * 时,前面都匹配到有效的字符

解题思路

方法一:递归

递归方法是理解这个问题的一个很好的起点,它可以直观地将问题分解为更小的子问题来解决。

解题步骤

1. 基本情况:如果模式 p 为空,成功匹配取决于字符串 s 也为空。

2. 匹配第一个字符:检查 sp 的第一个字符是否匹配(考虑到 '.')。

3. 使用 '*':如果 p 的第二个字符是 '*',则有两种情况:

  • 我们跳过 '*' 和它之前的字符,因为 '*' 可以匹配零个字符;
  • 如果第一个字符匹配,移动字符串 s,因为 '*' 可以匹配多个字符。

4. 递归匹配剩余字符串:根据以上逻辑递归地匹配剩余的 sp

python示例
def isMatch(s: str, p: str) -> bool:
    # 如果模式为空,成功匹配取决于字符串也为空
    if not p:
        return not s
 
    # 检查s的第一个字符是否与p的第一个字符匹配
    first_match = bool(s) and p[0] in {s[0], '.'}
 
    # 如果p的长度大于1并且p的第二个字符是'*'
    if len(p) >= 2 and p[1] == '*':
        # 使用'*'匹配0个字符,或者第一个字符匹配且s向前移动一位
        return (isMatch(s, p[2:])) or first_match and isMatch(s[1:], p)
    else:
        # 如果没有'*',则直接移动s和p都向前移动一位
        return first_match and isMatch(s[1:], p[1:])
 
# 示例测试
print(isMatch("aa", "a*"))  # True
print(isMatch("mississippi", "mis*is*p*."))  # False

方法二:动态规划

动态规划是解决这个问题的关键方法,它可以有效地避免重复计算,并且处理复杂的 '*' 匹配规则。

解题步骤

1. 初始化DP表:创建一个 (len(s) + 1) x (len(p) + 1) 大小的二维列表 dpdp[i][j] 表示字符串 s 的前 i 个字符与模式 p 的前 j 个字符是否能够匹配。初始化所有元素为 False

2. 基础情况:空字符串和空模式是匹配的,因此 dp[0][0] = True。然后初始化模式 p 中连续的 '*' 对应的状态,因为 '*' 可以取消前一个字符

3. 填充DP表:遍历 sp,对每一对字符更新 dp[i][j]

  • 如果p[j-1]'*',则有两种情况:
  • '*' 取消前一个字符(即模式 p 跳过两个字符),这时 dp[i][j] 取决于 dp[i][j-2]
  • 使用 '*' 匹配 s 中的多个字符,这时如果 s[i-1]p[j-2] 匹配,dp[i][j] 取决于 dp[i-1][j]
  • 如果 p[j-1]'.' 或者 s[i-1]p[j-1] 相等,dp[i][j] 取决于 dp[i-1][j-1]

4. 返回结果:表格的最后一个元素 dp[-1][-1] 表示整个字符串 s 与模式 p 是否匹配。

python示例
def isMatch(s: str, p: str) -> bool:
    # 初始化DP表,dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
 
    # 空字符串与空模式是匹配的
    dp[0][0] = True
 
    # 处理模式p的前缀为'*'的情况
    for j in range(1, len(p) + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]
 
    # 填充DP表
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            # 当前模式字符为'*'
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
            # 当前模式字符为'.'或者与字符串字符相同
            else:
                dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
 
    return dp[-1][-1]
优缺点
  • 优点
  • 动态规划避免了重复计算,大大提高了效率;
  • 明确地定义了所有状态转移情况,使得算法具有良好的结构性和可读性。
  • 缺点
  • 动态规划的空间复杂度较高,特别是当 sp 长度较大时;
  • 对于初学者来说,理解动态规划的状态转移可能稍显复杂。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
3天前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
24 8
|
5天前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
16 3
|
3天前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
|
4天前
|
算法 程序员 Python
算法小白到大神的蜕变之路:Python分治法、贪心、动态规划,一步步带你走向算法巅峰!
【7月更文挑战第9天】探索算法之旅,以Python解锁编程高手之路。分治法如二分查找,将复杂问题拆解;贪心算法解决活动选择,每次选取局部最优;动态规划求斐波那契数列,避免重复计算,实现全局最优。每一步学习,都是编程能力的升华,助你应对复杂挑战,迈向算法大师!
10 1
|
4天前
|
存储 算法 Python
Python算法界的秘密武器:分治法巧解难题,贪心算法快速决策,动态规划优化未来!
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解,如归并排序;贪心算法每步选局部最优解,不保证全局最优,如找零钱;动态规划存储子问题解求全局最优,如斐波那契数列。选择合适算法能提升编程效率。
13 1
|
4天前
|
存储 算法 Python
震撼!Python算法设计与分析,分治法、贪心、动态规划...这些经典算法如何改变你的编程世界!
【7月更文挑战第9天】在Python的算法天地,分治、贪心、动态规划三巨头揭示了解题的智慧。分治如归并排序,将大问题拆解为小部分解决;贪心算法以局部最优求全局,如Prim的最小生成树;动态规划通过存储子问题解避免重复计算,如斐波那契数列。掌握这些,将重塑你的编程思维,点亮技术之路。
13 1
|
4天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
5天前
|
算法 索引 Python
逆袭算法界!Python分治法、贪心算法、动态规划深度剖析,带你走出算法迷宫!
【7月更文挑战第8天】分治法,如快速排序,将大问题分解并合并解;贪心算法,选择局部最优解,如活动选择;动态规划,利用最优子结构避免重复计算,如斐波那契数列。Python示例展示这些算法如何解决实际问题,助你精通算法,勇闯迷宫。
14 1
|
5天前
|
算法 索引 Python
Python算法设计与分析大揭秘:分治法、贪心算法、动态规划...掌握它们,让你的编程之路更加顺畅!
【7月更文挑战第8天】探索Python中的三大算法:分治(如快速排序)、贪心(活动选择)和动态规划(0-1背包问题)。分治法将问题分解求解再合并;贪心策略逐步求局部最优;动态规划通过记忆子问题解避免重复计算。掌握这些算法,提升编程效率与解决问题能力。
15 1
|
3天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题