Regular Expression Matching

Q: 正则表达式匹配的时间复杂度是多少？

对于长度为 n 的字符串和长度为 m 的模式，表格解法的运行时间为 O(n × m) ，因为每个单元格最多读取另外两个单元格。完整表格需要 O(n × m) 的内存，使用两行则需要 O(m) 的内存。对于包含许多星号的模式，普通递归可能需要指数级的时间。

Q: 这与通配符匹配有什么不同？

在通配符匹配中，和文件名模式一样， * 独立使用，可以匹配任意一串字符， ? 匹配一个字符。这里的 * 只会重复它前面的元素，而任意文本都写作 .* 。两者都会使用一个基于前缀的表，但通配符星号会读取 dp[i][j-1] 或 dp[i-1][j] 。

困难动态规划递归

+10

给定一个字符串 s 和一个模式 p。在模式中，字母匹配相同的字母，点 . 匹配任意一个字母，星号 * 表示它前面的元素（字母或点）出现零次或多次。如果模式与整个 s 匹配，则返回 true，否则返回 false。

函数

isMatch(s: string, p: string) → boolean

sstring: 要匹配的字符串，只包含小写字母
pstring: 字母、点和星号组成的模式
返回值boolean: 如果 p 与 s 的所有内容都匹配，则为 true，否则为 false

约束条件

1 ≤ s.length ≤ 1000
1 ≤ p.length ≤ 1000
s 只包含小写英文字母。
p 只包含小写英文字母、. 和 *。
每个 * 前面都是字母或 .，所以 p 永远不会以 * 开头，也不会连续出现两个星号。

示例

输入: s = "moon"p = "mo*n"
输出: true
解释: o*会匹配两个字母 o，所以 m、o* 和 n 正好拼成 moon。

输入: s = "tree"p = "t.e"
输出: false
解释: t.e 可以匹配 tre，也就是 tree 的开头，但最后一个 e 多出来了，而匹配必须覆盖整个 s。

输入: s = "sky"p = "z*s.*y"
输出: true
解释: z* 匹配零个 z，s 匹配 s，.* 匹配 k，而 y 匹配 y。

进阶

你也能支持 + 吗？它表示同一个表格中前面的元素可以出现一次或多次。

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

星号可以匹配任意数量的重复字符，具体数量取决于它后面的内容。把一个字母和它后面的星号看作一个整体，有两种操作：跳过它，或者匹配一个字母并停留在这个整体上。记录 s 的哪些前缀与 p 的哪些前缀匹配的表格，会尝试每一种选择。

从左侧开始匹配递归

结果正确，但无法在最大的测试中运行完毕

思路

比较后缀：match(i, j) 用来判断 s[i:] 是否匹配 p[j:]。没有星号的字母或点号必须匹配 s[i]，其余部分也必须匹配。单元 x* 可以取零个副本并跳过，也可以消耗 s[i] 并留在同一个单元，这就是一个星号可以匹配任意数量字母的方式。这两个分支涵盖了星号的所有选择，因此不会漏掉任何匹配。

每个星号都会把搜索分成两路。对于 30 个字母 a、十个 a*，然后再加一个 b，递归会尝试约 8.5 × 10^8 种在星号之间分配这些字母的方式，最后才回答 false，但不同的 (i, j) 对只有 (n+1) × (m+1) 个。

算法

用 match(i, j) 表示分别从 i 和 j 开始的后缀。
如果 j 超出 p 的末尾，返回 i 是否超出 s 的末尾。
将 first 设为：s[i] 存在，并且 p[j] 是 s[i] 或点号。
如果 p[j+1] 是星号，返回 match(i, j+2) 或 first and match(i+1, j)。
否则返回 first and match(i+1, j+1)。答案是 match(0, 0)。

def isMatch(s, p):
    n, m = len(s), len(p)

    def match(i, j):
        # Does s[i:] match p[j:]?
        if j == m:
            return i == n
        first = i < n and p[j] in (s[i], ".")
        if j + 1 < m and p[j + 1] == "*":
            # use p[j] zero times, or let it eat s[i] and stay on the same x*
            return match(i, j + 2) or (first and match(i + 1, j))
        return first and match(i + 1, j + 1)

    return match(0, 0)

填写前缀表

思路

令 dp[i][j] 表示 s 的前 i 个字母是否与 p 的前 j 个字符匹配。dp[0][0] 为 true。在第 0 行，空字符串只有在模式前缀中的每个元素都带有星号时才匹配，例如 z* 或 a*b*。

p[j-1] 处的字母或点必须与 s[i-1] 匹配，其余部分也必须匹配：也就是对角线上的 dp[i-1][j-1]。带有元素 x = p[j-2] 的星号有两种移动方式。零次匹配会舍弃 x*：dp[i][j-2]。如果 x 与 s[i-1] 匹配，再匹配一次，则保留相同的 x* 来匹配更短的字符串：dp[i-1][j]，也就是上方的单元格。每次匹配都是沿星号所在列向上移动一步。对于 sky 和 z*s.*y，z*s.* 这一列通过零次匹配与 s 匹配为 true，然后再分别向上移动一步匹配 sk 和 sky。

每个单元格都会读取上一行或左侧的单元格，因此按行填充时，这些值都已经就绪。

算法

创建一个包含 (n+1) × (m+1) 个 false 值的表 dp，并将 dp[0][0] 设为 true。
对于从 2 到 m 的 j，如果 p[j-1] 是星号且 dp[0][j-2] 为 true，则将 dp[0][j] 设为 true。
对于每个满足 i ≥ 1 且 j ≥ 1 的单元格，如果 p[j-1] 是星号，则将其设为 dp[i][j-2] 或（p[j-2] 与 s[i-1] 匹配且 dp[i-1][j] 为 true）。
否则，将其设为（p[j-1] 与 s[i-1] 匹配）且 dp[i-1][j-1] 为 true。
返回 dp[n][m]。

def isMatch(s, p):
    n, m = len(s), len(p)
    # dp[i][j]: do the first i letters of s match the first j characters of p?
    dp = [[False] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = True  # an empty pattern matches an empty string
    for j in range(2, m + 1):
        # an empty string matches only patterns like x*y*z*
        dp[0][j] = p[j - 1] == "*" and dp[0][j - 2]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = dp[i][j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and dp[i - 1][j]  # one more copy eats s[i-1]
                dp[i][j] = zero or more
            else:
                dp[i][j] = p[j - 1] in (s[i - 1], ".") and dp[i - 1][j - 1]
    return dp[n][m]

只保留两行

思路

第 i 行只读取第 i-1 行的两个单元格，即对角线上的单元格和上方的单元格，再加上本行中左侧相隔两个位置的单元格。保留两个数组 prev 和 cur，并在处理完 s 的每个字母后交换它们：零次复制对应 cur[j-2]，多复制一次对应 prev[j]，普通匹配对应 prev[j-1]。内存占用从大约 10^6 个单元格降到两行，每行 1001 个单元格。不能交换输入来缩短行的长度，因为字符串和模式串的作用不同。

算法

用表格的第 0 行填充 prev。
对于 s 中的每个字母，将 cur[0] 设为 false，并根据表格规则填充 cur[1..m]，读取上一行的 prev。
交换 prev 和 cur。
返回 prev[m]。

def isMatch(s, p):
    n, m = len(s), len(p)
    # prev[j]: do the letters of s before the current one match the first j characters of p?
    prev = [False] * (m + 1)
    prev[0] = True  # row 0: the empty string
    for j in range(2, m + 1):
        prev[j] = p[j - 1] == "*" and prev[j - 2]  # only patterns like x*y*z* match it
    for i in range(1, n + 1):
        cur = [False] * (m + 1)  # cur[0] stays False: an empty pattern matches no letters
        for j in range(1, m + 1):
            if p[j - 1] == "*":
                zero = cur[j - 2]  # use p[j-2] zero times
                more = p[j - 2] in (s[i - 1], ".") and prev[j]  # one more copy eats s[i-1]
                cur[j] = zero or more
            else:
                cur[j] = p[j - 1] in (s[i - 1], ".") and prev[j - 1]
        prev = cur
    return prev[m]

易错点和边界情况

让星号尽可能多地匹配字母。a*a 可以匹配 aaa，但贪婪的 a* 会消耗全部 3 个字母，导致最后一个 a 匹配失败。
读取 dp[i-1][j-2] 来匹配多一个副本。这样星号最多只能匹配一个字母，因此 aa 与 a* 匹配时会得到 false。
第一格之后仍将第 0 行设为 false。这样 b 与 a*b 匹配时会失败，因为 b 需要 a* 匹配空前缀。
将 s[i-1] 与星号比较，而不是与星号对应的元素 p[j-2] 比较。这样 a 与 a* 匹配时会失败。
在双行版本中没有将 cur[0] 重置为 false。交换后，它可能保留基准行中的 true，导致 aab 与 b 匹配时得到 true。

常见问题3

正则表达式匹配的时间复杂度是多少？

对于长度为 n 的字符串和长度为 m 的模式，表格解法的运行时间为 O(n × m)，因为每个单元格最多读取另外两个单元格。完整表格需要 O(n × m) 的内存，使用两行则需要 O(m) 的内存。对于包含许多星号的模式，普通递归可能需要指数级的时间。

这与通配符匹配有什么不同？

在通配符匹配中，和文件名模式一样，* 独立使用，可以匹配任意一串字符，? 匹配一个字符。这里的 * 只会重复它前面的元素，而任意文本都写作 .*。两者都会使用一个基于前缀的表，但通配符星号会读取 dp[i][j-1] 或 dp[i-1][j]。

为什么不使用该语言的正则表达式库？

面试官想看的是算法，而不是调用库。许多正则表达式引擎也会通过回溯来匹配，这和第一种方法中的缓慢递归类似，因此，用 10 个 a* 后接 b 去匹配一长串字母 a，可能会让它们运行几分钟。这个表总能在 O(n × m) 时间内完成。

def isMatch(s, p):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

s = "moon"
p = "mo*n"

预期输出

true