😀前言
正则表达式是一种强大的工具，广泛应用于文本匹配和处理。在许多编程任务中，我们可能会遇到需要匹配字符串与某个特定模式的情况。本文将介绍如何使用动态规划算法实现一个支持 . 和 * 的正则表达式匹配功能，并以 Java 为例进行代码实现。

🥰正则表达式匹配的动态规划算法解析

😃问题描述

给定一个字符串 str 和一个模式 pattern，要求实现一个函数来判断 str 是否匹配 pattern。其中，模式中包含的特殊字符有：

• .：匹配任意单个字符。
• *：匹配前一个字符任意次（包括 0 次）。

例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，但与模式 "aa.a" 和 "ab*a" 不匹配。

😆解题思路

要解决这个问题，我们可以使用动态规划来逐步构建匹配结果。动态规划的思想是将一个大问题拆解成一系列小问题，然后通过递归或迭代来解决这些小问题，从而得出最终结果。

😘 状态定义

我们定义一个二维数组 dp[m + 1][n + 1]，其中 dp[i][j] 表示字符串 str 的前 i 个字符与模式 pattern 的前 j 个字符是否匹配。

😘转移方程

1. 初始状态：

   • 当字符串和模式都为空时，显然是匹配的，因此 dp[0][0] = true。
   • 如果字符串为空但模式不为空，只有模式中的 * 可以匹配空字符串，因此我们需要初始化 dp[0][j]。如果模式的第 j 个字符是 *，那么它可以消去它前面的字符，因此 dp[0][j] = dp[0][j-2]。

2. 当 str[i-1] 与 pattern[j-1] 相等，或者 pattern[j-1] 是 . 时，dp[i][j] 可以继承 dp[i-1][j-1] 的值，因为当前字符匹配，匹配结果取决于前面部分的匹配情况。

   当 pattern[j-1] 是 * 时，有两种情况：

   1. * 将它前面的字符消掉，即 pattern[j-2] 可以被忽略，这时 dp[i][j] = dp[i][j-2]。
   2. 如果 str[i-1] 与 pattern[j-2] 相等，或者 pattern[j-2] 是 .，那么 * 可以代表一次或多次匹配，这时 dp[i][j] = dp[i-1][j] 或 dp[i][j] = dp[i][j-1]。

public class Solution {
    public boolean match(String str, String pattern) {
        int m = str.length(), n = pattern.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        // 初始化状态
        dp[0][0] = true;
        for (int j = 1; j <= n; j++) {
            if (pattern.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        // 动态规划填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前字符匹配，或者模式字符为 '.'
                if (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } 
                // 如果模式字符为 '*'
                else if (pattern.charAt(j - 1) == '*') {
                    // * 代表 0 次
                    dp[i][j] = dp[i][j - 2];
                    // * 代表 1 次或多次
                    if (pattern.charAt(j - 2) == str.charAt(i - 1) || pattern.charAt(j - 2) == '.') {
                        dp[i][j] |= dp[i - 1][j];
                    }
                }
            }
        }

        // 返回最终匹配结果
        return dp[m][n];
    }
}

😀代码解析

1. 初始化状态：
   • dp[0][0] = true 表示空字符串与空模式匹配。
   • 对于只有 * 的模式，初始化 dp[0][j] 为 dp[0][j-2]，表示 * 号匹配 0 次。
2. 动态规划填表：
   • 如果当前字符匹配（包括 . 的情况），那么直接继承 dp[i-1][j-1] 的结果。
   • 如果当前模式字符为 *，则有两种情况：
     1. * 表示 0 次匹配，则继承 dp[i][j-2]。
     2. * 表示 1 次或多次匹配，继承 dp[i-1][j]，并用 |= 操作将结果合并。
3. 返回结果：
   • 最终，dp[m][n] 存储了字符串 str 与模式 pattern 是否匹配的结果。

😊示例分析

以字符串 "aaa" 和模式 "ab*ac*a" 为例，算法通过动态规划的方式一步步验证每个字符与模式的匹配关系。最终，通过矩阵 dp 的计算，可以判断 "aaa" 与 "ab*ac*a" 匹配。

😊时间与空间复杂度

• 时间复杂度：O(m * n)，其中 m 是字符串的长度，n 是模式的长度。动态规划矩阵的每个元素都需要被填充一次，因此时间复杂度为 O(m * n)。
• 空间复杂度：O(m * n)，需要一个二维矩阵存储动态规划的结果。

😄总结

本文介绍了一种基于动态规划的正则表达式匹配算法，能够有效处理带有 . 和 * 的复杂模式匹配问题。通过构建和解析状态转移方程，该算法可以在多种匹配场景下表现出色，并且具有线性时间和空间复杂度，适合大规模数据的匹配任务。