题目描述

给你一个字符串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的小写字母，以及字符.和*。
• 保证每次出现字符*时，前面都匹配到有效的字符

题目链接：https://leetcode.cn/problems/regular-expression-matching/description/

『1』动态规划

解题思路：

参考题解：『 动态规划 』字符串 DP 详解：状态转移推导 + 滚动优化 + 提前结束

实现代码：

class Solution {
    // Dynamic Programming
    // M is the length of s
    // N is the length of p
    // Time Complexity: O(M*N)
    // Space Complexity: O(M*N)
    public boolean isMatch(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();
        int n = cs.length, m = cp.length;

        // dp[i][j] 表示 p 的前 j 个字符能否匹配 s 的前 i 个字符
        boolean[][] dp = new boolean[n + 1][m + 1];
        // 初始化 dp 数组
        // s 为空，p 为空，能匹配上
        dp[0][0] = true;
        // s 不空，p 为空，只能为 false（默认值不需处理）
        // s 为空，p 不空，由于 * 可以匹配 0 个字符，所以有可能为 true，需要进行初始化
        for (int j = 1; j <= m; j++) {
            if (cp[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (cp[j - 1] == '*') {
                    if (matches(cs, cp, i, j - 1)) {
                        // 匹配 0 次的情况 + 匹配 1 次或多次的情况
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    } else {
                        // 只能匹配 0 次
                        dp[i][j] = dp[i][j - 2];
                    }
                } else {
                    if (matches(cs, cp, i, j)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[n][m];
    }

    boolean matches(char[] cs, char[] cp, int i, int j) {
        if (cp[j - 1] == '.') return true;
        return cs[i - 1] == cp[j - 1];
    }
}