[LeetCode] 10. Regular Expression Matching 题解

问题描述

输入字符串 (s) 和模式 (p),实现支持 '.''*' 的正则表达式。

'.' 能匹配任意单字符
'*' 能匹配 0 个或多个该符号前面的字符

匹配需覆盖整个字符串 (而不是一部分)。

注意:

  • s 为只包含 a-z 的字符串,且它可以为空
  • p 为只包含 a-z.* 的字符串,且它可以为空

例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 不能匹配整个字符串 "aa"

例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 意味着 0 到多个前置元素 - 'a'。 因此,将 'a' 重复 1 次,即 "aa"。

例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 意为着 "0 个或多个 (*) 任意的字符 (.)"。

例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: "c*" 可以表示将 c 重复 0 次,a 可以重复 1 次,因此得到 "aab"。

例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

问题难度

Hard

解题思路

本题是名副其实的 Hard,因为没有特别好的思路,我也是求助于 Solution,下面会描述 Solution 中的 2 种解题思路:

方法 1:递归法

这题难在 * 符号的处理上,如果没有该符号,程序会简单很多,你只需要递归匹配每个字符即可,如下:

# 无 * 的情况
class Solution(object):
    def isMatch(self, s, p):
        if not p: return not s

        firstMatch = True if s and p[0] in {s[0], '.'} else False
        return firstMatch and self.isMatch(s[1:], p[1:])

增加了 * 的支持后,该符号会增加两种操作:

  1. 如 s 当前字符与 * 前面的字符不匹配,则删除 p 中的 * 及其前面的 1 个字符,例如上面 例 4 中的 c*
  2. 否则删除 s 中与 * 之前字符相匹配的 1 个字符

为了涵盖这 2 种操作,以上代码可改为:

class Solution(object):
    def isMatch(self, s, p):
        if not p: return not s

        firstMatch = True if s and p[0] in {s[0], '.'} else False
        
        if len(p) > 1 and p[1] == "*":
            # 对 * 处理的 2 种操作
            return firstMatch and self.isMatch(s[1:], p) or self.isMatch(s, p[2:])
        else:        
            return firstMatch and self.isMatch(s[1:], p[1:])	

方法 2:动态规划

保留方法 1 的思路,同时利用动态规划的思想,把 sp 匹配过的结果缓存下来,这样当重复的 s[i:]p[j:] 出现时,可以直接从缓存中读取,减少重复计算的开销:

class Solution(object):
    def isMatch(self, s, p):
        mem = {}
        def dp(i, j):
            if (i, j) in mem:
                return mem[(i, j)]

            if j >= len(p):
                res = i >= len(s)
            else:
                first_match = i <= len(s) - 1 and p[j] in {s[i], '.'}
                if j <= len(p) - 2 and p[j+1] == '*':
                    res = dp(i, j+2) or first_match and dp(1+i, j)
                else:
                    res = first_match and dp(1+i, 1+j)

            mem[(i, j)] = res
            return res
        return dp(0, 0)

原题链接