欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer最新版_剑指 Offer 19. 正则表达式匹配 leetcode 剑指offer系列

程序员文章站 2022-04-23 22:17:35
...
剑指offer最新版_剑指 Offer 19. 正则表达式匹配 leetcode 剑指offer系列点击专辑上方“蓝字”关注我吧

题目难度: 困难

原题链接[1]

今天继续更新剑指 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. 如何特殊处理.*?

解决方案

思路

分析

  • 分析题目, 特殊字符只有.*. .比较简单, 直接可以跟任何字符匹配; 而*则要考虑前一个字符是什么.
  • 要判断两个字符串是否匹配, 最简单的做法就是双指针依次比较即可, 这里也不例外.
  • 我们需要维护当前 sp 的下标 ij, 然后从起点开始匹配, 分为以下几种情况分析:
  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]相等时才成功匹配.
  1. 边界情况 1: p 的字符已经用完, 即 j == len(p). 此时只有当 s 也恰好匹配完, 才表明两个字符串匹配;
  2. 边界情况 2: s 的字符已经用完, 即 i == len(s). 这种情况下, 如果 p 也恰好匹配完显然匹配; 但 p 没有用完的时候也可能匹配. 这是因为有*的存在, 它和它前一个字符可以只匹配 0 次, 这就意味着只有当前 p 之后的字符串满足x*x*这样的形式就也可以匹配;
  3. 此时 ps 的字符都还有剩余, 这时候不能简单比较 s[i]p[j], 这是因为有*的存在, 需要继续细分为两种情况:
注意我们在判断过程中可以将 (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 and p[j + 1] == '*':
                        memo[i, j] = match(i, j + 2)
                    else:
                        memo[i, j] = False
                else:
                    # 意味着s和p都没遍历完
                    if j + 1 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)

参考资料

[1]

原题链接: https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

剑指offer最新版_剑指 Offer 19. 正则表达式匹配 leetcode 剑指offer系列剑指offer最新版_剑指 Offer 19. 正则表达式匹配 leetcode 剑指offer系列剑指offer最新版_剑指 Offer 19. 正则表达式匹配 leetcode 剑指offer系列 你的每个赞和在看,我都喜欢! 剑指offer最新版_剑指 Offer 19. 正则表达式匹配 leetcode 剑指offer系列
相关标签: 剑指offer最新版