【极简动态规划正则表达式匹配】

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

【Java 刷题打卡】刷题比玩游戏好多了，成就感越来越强，每天坚持刷几道题，每天锻炼30分钟，等8块腹肌,等大厂offer.

那就干吧！这个专栏都是刷的题目都是关于动态规划的,我会由浅入深、循序渐进，刷题就是这样需要连续不断的记忆–艾宾浩斯记忆法2121112。动态规划的内容不多，但是都是每个程序员必备的

$\color{green}{这道题很经典啦? ? ? ~}$

刷题之路，任重而道远啊

什么题可以选择动态规划来做？

1.计数

有多少种方式走到右下角
有多少种方法选出k个数是的和是sum

2.求最大值最小值

从左上角走到右下角路径的最大数字和
最长上升子序列长度

3.求存在性

取石子游戏,先手是否必胜
能不能选出k个数使得和是sum

题目一

leecode 10. 正则表达式匹配

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

‘.’ 匹配任意单个字符

‘*’ 匹配零个或多个前面的那一个元素

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

示例 1：

输入：s = “aab” p = “cab”

输出：true

解释：因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 2：

输入：s = “mississippi” p = “misisp*.”

输出：false

解释：第二个*不能匹配si

2.1. 动态规划组成部分1：确定状态

wc，你倒是说说怎么确定要用动态规划来做啊？

看题目，需要逐步匹配
没有时间复杂度空间复杂度限制，你可以选择>On的
跟前面题很类似，这里需要考虑* 和 .的情况。
尝试根据步骤写出转移方程

在这道题中，我们定义f[i][j] 表示字符串 s 的前 i 个字符与字符串p的前 j 个字符是否匹配

解动态规划需要两个意识：

最后一步
子问题

最后一步

我们用示例来讲解：s = “aaab” p = “aa*b”

根据题目意思，我们知道s要被全匹配，我们直接用s去匹配p字符串的每一个字符，这样我们的最后一步就是用s字符串中的b字符去匹配p字符串的每一个字符，匹配最后一个字符为b是否相等。

子问题

有几种情况需要讨论，也就是用s去匹配p最后一个匹配的字符j

如果都是字符，只需要判断：f[i][j] = f[i-1][j-1]
如果是“.” ,说明可以匹配s的最后任意一个字符，也只需：

f[i][j] = f[i-1][j-1]
如果是“*”，分两种情况一种是匹配零个字符，一种是匹配1个或多个字符

如果是匹配零个字符：f[i][j] = f[i][j-2] ，因为如果j是*，我们就可以对p的j-1匹配任意次数，当然零次就是j-2了。

如果是匹配1个或多个字符：f[i][j] = f[i-1][j]，匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配,简单点说，零个我们判定了，如果是一个我们扔掉一个字符，如果能匹配则保存，如果匹配两个，我们是知道匹配s的上一个字符的结果的，直接匹配就行，同样匹配多个也是如此。（匹配多个是根据前一个的匹配结果得出来的）

2.2. 动态规划组成部分2：转移方程

在子问题中我们分析的几种情况就是转移方程

2.3. 动态规划组成部分3：**初始条件和边界情况

因为要涉及到i-1和j-1，注意边界

boolean[][] f = new boolean[m + 1][n + 1];

f[0][0]=true

2.4. 动态规划组成部分4：计算顺序

用s去匹配p字符串的每一个字符

它的时间复杂度是Onm,由于是二维数据空间复杂度是Onm

参考代码

public boolean isMatch(String s, String p) {
    int m = s.length();
    int n = p.length();

    boolean[][] f = new boolean[m + 1][n + 1];
    f[0][0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) == '*') {
                f[i][j] = f[i][j - 2];
                if (matches(s, p, i, j - 1)) {
                    f[i][j] = f[i][j] || f[i - 1][j];
                }
            } else {
                if (matches(s, p, i, j)) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
    }
    return f[m][n];
}

public boolean matches(String s, String p, int i, int j) {
    if (i == 0) {
        return false;
    }
    if (p.charAt(j - 1) == '.') {
        return true;
    }
    return s.charAt(i - 1) == p.charAt(j - 1);
}
@Test
public void isisMatch() {
     boolean i = isMatch("aa", "a*");
     Assert.assertNotNull(i);
}
复制代码