题目难度: 困难

原题链接

今天继续更新剑指 offer 系列, 这道题是这个系列的第一道困难题, 也是非常经典的题目了

老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了

题目描述

请实现一个函数用来匹配包含.和*的正则表达式。模式中的字符.表示任意一个字符，而*表示它前面的字符可以出现任意次（含 0 次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

题目样例

示例 1

输入

s = "aa"
p = "a"

输出

false

解释

"a" 无法匹配 "aa" 整个字符串。

示例 2

输入

s = "aa"
p = "a*"

输出

true

解释

因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3

输入

s = "aab"
p = "c*a*b"

输出

true

解释

因为 * 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

题目思考

  1. 如何特殊处理.和*?

解决方案

思路

分析

  • 分析题目, 特殊字符只有.和*. .比较简单, 直接可以跟任何字符匹配; 而*则要考虑前一个字符是什么.
  • 要判断两个字符串是否匹配, 最简单的做法就是双指针依次比较即可, 这里也不例外.
  • 我们需要维护当前 s 和 p 的下标 i 和 j, 然后从起点开始匹配, 分为以下几种情况分析:
    1. 边界情况 1: p 的字符已经用完, 即 j == len(p). 此时只有当 s 也恰好匹配完, 才表明两个字符串匹配;
    2. 边界情况 2: s 的字符已经用完, 即 i == len(s). 这种情况下, 如果 p 也恰好匹配完显然匹配; 但 p 没有用完的时候也可能匹配. 这是因为有*的存在, 它和它前一个字符可以只匹配 0 次, 这就意味着只有当前 p 之后的字符串满足x*x*这样的形式就也可以匹配;
    3. 此时 p 和 s 的字符都还有剩余, 这时候不能简单比较 s[i] 和 p[j], 这是因为有*的存在, 需要继续细分为两种情况:
      1. 如果 p[j+1] 存在且为*: 此时s[i] 可以直接跳到与p[j+2]匹配, 表示不用当前的x*组合; 当然也可以 j 不动而 i 继续后移 (前提是s[i] 和 p[j]匹配)
      2. 否则的话意味不能跳过, 必须比较 s[i] 和 p[j], 只有p[j]为.或者和s[i]相等时才成功匹配.
  • 注意我们在判断过程中可以将(i, j)组合的结果保存起来, 避免重复计算, 这就是记忆化搜索的思想

实现

  • 下面代码完全基于上述分析实现, 必要步骤都有详细注释

复杂度

  • 时间复杂度 O(MN)
    • 采用了记忆化方法, 每个字符只需要计算一次匹配
  • 空间复杂度 O(MN)
    • 需要存所有下标组合的匹配结果

代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # 记忆化搜索
        memo = {}

        def match(i, j):
            # 如果(i, j)已经在memo中就不要重复计算了
            if (i, j) not in memo:
                if j == len(p):
                    # 模式串p遍历完了, 那么只有当s正好也遍历完才满足要求
                    memo[i, j] = i == len(s)
                elif i == len(s):
                    # 此时意味着s遍历完了, 但模式串p仍然有值, 这时候只有当后面的模式串都是x*x*这样的形式才可以, 代表后面的x*都只匹配0次
                    # 所以需要判断p[j+1]是否是*, 是的话继续递归判断(i,j+2)组合, 否则直接返回False
                    if j + 1 < len(p) and p[j + 1] == '*':
                        memo[i, j] = match(i, j + 2)
                    else:
                        memo[i, j] = False
                else:
                    # 意味着s和p都没遍历完
                    if j + 1 < len(p) and p[j + 1] == '*':
                        # 下一个p字符是*, 意味着当前字符可以不使用, 首先考虑这种情况
                        memo[i, j] = match(i, j + 2)
                        if s[i] == p[j] or p[j] == '.':
                            # 但如果当前字符恰好匹配的话, 也可以使用它, j位置保持不变, i后移
                            memo[i, j] |= match(i + 1, j)
                    else:
                        # 下一个p字符不是*, 必须老老实实根据当前字符匹配了
                        memo[i, j] = (s[i] == p[j] or p[j] == '.') and match(
                            i + 1, j + 1)
            return memo[i, j]

        return match(0, 0)

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 每日精选算法题, 欢迎大家扫码关注~😊

每日精选算法题 - 微信扫一扫关注我