[LeetCode 程序员内功修炼系列] 10. Regular

问题描述

输入字符串 (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 的思路，同时利用动态规划的思想，把 s 和 p 匹配过的结果缓存下来，这样当重复的 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)

原题链接