模糊搜索验证

难度: Hard

请设计一个程序来支持用户在文本编辑器中的模糊搜索功能。用户输入内容中可能使用到如下两种通配符：

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的那一个元素。

请返回用户输入内容 input 所有字符是否可以匹配原文字符串 article。

示例 1:

输入: article = "aa", input = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

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

示例 3:

输入: article = "ab", input = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

1 <= article.length <= 20
1 <= input.length <= 20
article 只包含从 a-z 的小写字母。
input 只包含从 a-z 的小写字母，以及字符 . 和 * 。
保证每次出现字符 * 时，前面都匹配到有效的字符

注意：本题与主站 10 题相同：https://leetcode-cn.com/problems/regular-expression-matching/

Submission

运行时间: 48 ms

内存: 15 MB

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        memo = dict()

        def dp(i, j):
            if j == n:
                return i == m
            if i == m:
                if (n - j) % 2 == 1:
                    return False
                while j + 1 < n:
                    if p[j+1] != "*":
                        return False
                    j += 2
                return True

            if (i, j) in memo:
                return memo[(i, j)]

            res = False

            if s[i] == p[j] or p[j] == '.':
                if j + 1 < n and p[j+1] == '*':
                    res = dp(i, j+2) or dp(i+1, j)
                else:
                    res = dp(i+1, j+1)
            else:
                if j + 1 < n and p[j+1] == '*':
                    res = dp(i, j+2)
                else:
                    res = False

            memo[(i, j)] = res
            return res

        return dp(0, 0)

Explain

此题解采用了动态规划（DP）的方法来解决正则表达式匹配问题。解决方案通过递归函数 dp(i, j) 检查原始字符串 s 从位置 i 开始的子串是否可以被模式 p 从位置 j 开始的子串匹配。使用 memoization 技术（memo 字典）来避免重复计算相同参数的函数调用，从而提高效率。对于基本情况，当模式 p 已经全部匹配完毕 (j == n)，检查 s 是否也完全匹配 (i == m)。若 p 未结束但 s 已结束，则检查剩余的 p 是否可以匹配空字符串。递归地处理模式中的特殊字符 '*' 和 '.'，其中 '.' 可以匹配任意单个字符，'*' 表示前一个字符可以出现零次或多次。

时间复杂度: O(m*n)

空间复杂度: O(m*n)

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        memo = dict()

        def dp(i, j):
            # 如果 p 已全部匹配完毕，检查 s 是否也匹配完毕
            if j == n:
                return i == m
            # 如果 s 已结束但 p 未结束，检查 p 是否可匹配空字符串
            if i == m:
                if (n - j) % 2 == 1:
                    return False
                while j + 1 < n and p[j+1] == '*':
                    j += 2
                return True

            if (i, j) in memo:
                return memo[(i, j)]

            res = False

            # 处理匹配操作，考虑 '.' 和 '*' 的情况
            if s[i] == p[j] or p[j] == '.':
                if j + 1 < n and p[j+1] == '*':
                    res = dp(i, j+2) or dp(i+1, j)  # 跳过模式或匹配多次
                else:
                    res = dp(i+1, j+1)  # 正常匹配下一字符
            else:
                if j + 1 < n and p[j+1] == '*':
                    res = dp(i, j+2)  # 跳过带 '*' 的模式部分
                else:
                    res = False

            memo[(i, j)] = res
            return res

        return dp(0, 0)

Explore

在此动态规划解法中，初始条件基于字符串 `s` 和 `p` 的结束情况来定义。如果模式 `p` 已经检查完毕（即 `j == n`），则必须检查字符串 `s` 是否也已经结束 (`i == m`)，这是基础匹配条件。状态转移方程基于当前字符和模式的匹配情况而定，特别是考虑到模式字符 '.' 和 '*' 的处理。'.' 匹配任意单个字符，而 '*' 表示其前一个字符可以出现零次或多次，这导致多个分支的递归调用，形成了状态转移的逻辑。

`dp(i, j+2)` 代表在模式 `p` 中跳过当前的字符和其后的 '*'，这反映了 '*' 的零次出现场景。`dp(i+1, j)` 表示当前字符在 `s` 中匹配后，继续在 `p` 中使用相同的模式进行匹配，这反映了 '*' 的多次出现场景。这两种处理方式是必需的，因为 '*' 的语义允许前一个字符出现任意次，从零次到多次。

当 `s` 结束但 `p` 未结束时，我们需要检查 `p` 剩余部分是否能匹配空串。`'(n - j) % 2 == 1'` 检查是因为，如果 `p` 中剩余字符数为奇数，那么这些字符不能完全由 '字符+*' 的组合构成（因为每个这样的组合都占两个位置），从而无法匹配空串。该检查帮助确定是否有非法的单独字符存在，这些字符无法通过 '*' 来抵消其影响。

这个循环的目的是处理模式中的冗余 '*' 字符。在模式匹配中，如果一个字符后面直接跟着多个 '*'，这是语法上的冗余，因为一个 '*' 已经足够表示其前字符的零次或多次出现。这个循环通过跳过多余的 '*'，简化模式字符串，确保每个字符后面最多只跟一个 '*'，从而避免解析上的混乱和潜在的错误处理。