leetcode第十题:正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

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

所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

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

示例 3：

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

提示：

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

步骤 1：问题性质分析

输入输出条件：

• 输入：
  • 字符串 s：需要匹配的目标字符串，长度为 m。
  • 字符串 p：表示匹配模式，长度为 n，其中包含两种特殊字符：
    • .：匹配任意单个字符。
    • *：匹配零个或多个前面的那个字符。
• 输出：
  • 返回 true 或 false，表示 p 是否可以完整匹配字符串 s。

问题特性：

1. 匹配必须涵盖整个字符串 s，不能是部分匹配。
2. 模式中的 . 可以匹配任意单个字符，* 可以匹配零个或多个前面的字符。
3. 边界情况：
   • 当 s 或 p 为空字符串时，需要特别处理。
   • 如果 p 中存在 *，需要确定其前置字符能否匹配到 s 中的对应字符。

潜在边界条件：

• s 为空且 p 为空，返回 true。
• s 不为空而 p 为空，返回 false。
• 处理 * 前置字符为 . 或非 . 的不同情况。

步骤 2：解题步骤与算法设计

对于此题，最佳的解决思路是采用 动态规划 方法。动态规划可以有效处理子问题的重叠，避免重复计算，并逐步构建从简单到复杂的匹配结果。

动态规划的核心思想：

1. 状态定义：定义一个布尔二维数组 dp[i][j]，表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。
2. 状态转移方程：
   • 如果 p[j-1] 是普通字符或是 .，则：
     • dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.')
   • 如果 p[j-1] 是 *，它可以匹配零个或多个前面的字符，则需要考虑两种情况：
     • 匹配零个前面的字符：dp[i][j] = dp[i][j-2]
     • 匹配一个或多个前面的字符：dp[i][j] = dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')
3. 初始化：
   • dp[0][0] = true，表示空字符串和空模式匹配。
   • 对于空字符串 s，如果模式 p 能够匹配零个字符的情况（如 a* 或 a*b*），则 dp[0][j] 需要根据前面字符的情况进行初始化。
4. 最终结果：dp[m][n] 表示 s 和 p 的整体匹配结果。

动态规划算法的时间复杂度与空间复杂度：

• 时间复杂度：O(m * n)，其中 m 是字符串 s 的长度，n 是模式 p 的长度。
• 空间复杂度：O(m * n)，需要二维数组来保存中间结果。

步骤 4：算法优化启发

1. 优化思路：在大型字符串和复杂模式下，可以通过滚动数组优化空间复杂度，将 dp 数组压缩为一维数组。通过观察，可以发现只需存储前一行的状态，因此可以用两个一维数组来交替更新，空间复杂度可以降低为 O(n)。
2. 效率提升：通过动态规划避免了递归或暴力回溯的重复计算问题，大大提升了处理大规模数据集的效率。

步骤 5：实际应用场景

正则表达式匹配算法在多个领域有广泛的应用，尤其在需要进行复杂模式匹配的场景中具有重要作用。以下是一个实际的应用场景：

实际应用示例：文本搜索和过滤

在大规模的文本数据处理中，正则表达式匹配被广泛用于日志分析、字符串匹配、敏感词过滤等。比如在 网络安全 领域，利用该算法可以在海量的日志文件中快速识别出潜在的攻击模式或特定的安全事件。

具体实现方法：

1. 日志系统通过正则表达式来过滤出具有攻击特征的日志条目。模式可能包含通配符（对应 . 和 *）来捕捉多种变种攻击的表达方式。
2. 通过优化后的动态规划算法，能够快速匹配出符合攻击模式的日志条目，提升整个安全系统的响应速度。