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

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

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

欢迎加入社区：

作者专栏每日更新：

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

备注说明：方便大家阅读，统一使用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. 匹配第一个字符：检查 s 和 p 的第一个字符是否匹配（考虑到 '.'）。

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

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

4. 递归匹配剩余字符串：根据以上逻辑递归地匹配剩余的 s 和 p。

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) 大小的二维列表 dp。dp[i][j] 表示字符串 s 的前 i 个字符与模式 p 的前 j 个字符是否能够匹配。初始化所有元素为 False。

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

3. 填充DP表：遍历 s 和 p，对每一对字符更新 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]

优缺点

• 优点：

• 动态规划避免了重复计算，大大提高了效率；
• 明确地定义了所有状态转移情况，使得算法具有良好的结构性和可读性。

• 缺点：

• 动态规划的空间复杂度较高，特别是当 s 和 p 长度较大时；
• 对于初学者来说，理解动态规划的状态转移可能稍显复杂。

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