正则表达式匹配

力扣 10. 正则表达式匹配

题目说明

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

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

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

提示：
- 0 <= s.length <= 20
- 0 <= p.length <= 30
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
- 保证每次出现字符 * 时，前面都匹配到有效的字符

示例

示例 1:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

1
2
3

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

示例 4:

1
2
3

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

笔者理解

此题是一道字符串匹配算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，发现我们可以使用动态规划来求解，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 动态规划
     * 字符串
     */
    public boolean isMatch(String s, String p) {
        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();

        // dp[i][j]: 表示s的前i个字符, p的前j个字符是否能够匹配
        boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];

        // s, p 都为空的时候是匹配的, 而其他都预设是不匹配的
        dp[0][0] = true;

        // 当某位字符为 * 时, 它可以抵消前一个字符, 所以存在下述转移式
        for (int i = 1; i <= cp.length; i++) {
            if (cp[i - 1] == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }

        // 比较两个字符
        for (int i = 1; i <= cs.length; i++) {
            for (int j = 1; j <= cp.length; j++) {
                // 当两个字符相等 or p 字符串当前字符串是万能字符 .
                if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
                    // 可以直接抵消, 等于上次的结果
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 当匹配到 * 时
                else if (cp[j - 1] == '*') {
                    // 字符串s * 的前一个字符能够跟字符串p 的末位匹配上时
                    if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
                        // 对应的两种状态:
                        // dp[i][j] = dp[i][j - 2] 匹配 0 次
                        // dp[i][j] = dp[i - 1][j] 匹配 1到多 次
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }
                    // 不能匹配
                    else {
                        // 只能匹配 0 次
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }

        return dp[cs.length][cp.length];
    }
}