【DP】正则表达式｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目概述

LeetCode 10. 正则表达式匹配

给你一个字符串 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
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4：

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

输入：s = "mississippi" p = "mis*is*p*."
输出：false
复制代码

提示：

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

题干分析

面对两个待匹配字符 s[i] 和 p[j], 看是否匹配：

boolean isMathc(String s, String p) {
    int i = 0, j = 0;
    while(i < s.length && j < p.length) {
        // "." 通配符是万金油
        if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
            ++i;
            ++j;
        } else {
           // 不匹配
           return false;
        }
    }
    return i == j;
}
复制代码

加入 "*" 通配符，当 p[j + 1] 为 * 通配符时，分情况讨论：

1. 当 s[i] == p[j]，那么有两种情况：

   1. p[j] 有可能匹配多个字符，比如 s = "aaa", p = "a*"，那么 p[0] 会通过 * 匹配 3个字符 "a"

   2. p[i] 也有可能匹配 0 个字符，比如 s = "aa", p = "a*aa", 由于后面的字符可以匹配 s, 所以 p[0] 只能匹配 0 次。

2. 当 s[i] != p[j] ，只有一种情况：

p[j] 只能匹配 0 次，然后看下一个字符是否能和 s[i] 匹配。比如 s = "aa", p = "b*aa", 此时 p[0] 只能匹配 0 次。

如图：

if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
    // 匹配
    if (j < p.size() - 1 && p.charAt(j + 1) == '*') {
        // 有 * 通配符，可以匹配 0 次或多次
    } else {
        // 无 * 通配符, 老老实实匹配 1 次
        ++i;
        ++j;
    }
} else {
    // 不匹配
    if (j < p.size() - 1 && p.charAt(j + 1) == '*') {
        // 有 * 通配符，只能匹配 0 次
    } else {
        // 无 * 匹配无法进行下去了
        return false;
    }
}
复制代码

那么主要问题就是：遇到 * 通配符时，到底应该匹配 0 次还是匹配多次？多次是几次？

动态规划标准套路：

1. 第一步要明确：状态 和 选择
2. 第二步要明确：dp 数组的定义
3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 第一步要明确：状态 和 选择

1. 状态：i 和 j 两个指针
2. 选择：p[j] 选择匹配几个字符

2. 第二步要明确：dp 数组的定义

1. dp数组的定义：dp[i][j] = true 表示匹配成功

2. 最终答案：dp[M][N]

3. base case：dp[0][0] = true 和 dp[i][0] = false 和 dp[]

3. 第三步：根据 “选择”，思考状态转移的逻辑

二、实现分析

实现有：

1. 递归子串判别

2. dp 判断

3. 递归子串判别

public class LeetCode_10 {

    // Faster: 11.51%
    public boolean isMatch(String s, String p) {

        // 正则串为空
        if (p.isEmpty()) {

            return s.isEmpty();
        }

        // 正则串长度为 1
        if (p.length() == 1) {

            return (s.length() == 1 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
        }

        // 正则串第二个字符不是 *
        if (p.charAt(1) != '*') {

            if (s.isEmpty()) {

                return false;
            }

            return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
        }

        while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {

            if (isMatch(s, p.substring(2))) {
                return true;
            }

            s = s.substring(1);
        }

        return isMatch(s, p.substring(2));
    }
}
复制代码

2. dp 判断

public class LeetCode_10 {

    // Time: O(m*n), Space: O(m*n), Faster: 99.58%
    public boolean isMatchDP(String s, String p) {
        if (s == null || p == null) return false;
        int m = s.length(), n = p.length();
        boolean[][] d = new boolean[m+1][n+1];

        // base case
        d[0][0] = true;
        for (int i = 1; i <= m; ++i)
            d[i][0] = false;
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j-1) == '*') d[0][j] = d[0][j-2];
            else d[0][j] = false;
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                char sc = s.charAt(i-1), pc = p.charAt(j-1);
                if (isEqual(sc, pc)) {
                    d[i][j] = d[i-1][j-1];
                } else if (pc == '*') {
                    char preChar = p.charAt(j-2);
                    if (isEqual(sc, preChar)) d[i][j] = d[i][j-2] || d[i][j-1] || d[i-1][j];
                    else d[i][j] = d[i][j-2];
                } else {
                    d[i][j] = false;
                }
            }
        }
        return d[m][n];
    }

    private boolean isEqual(char sc, char pc) {
        return sc == pc || pc == '.';
    }
}
复制代码