我的原文链接：http://ben-personal.top/2020/03/leetcode-10-regex/

本题要求实现一个简单的正则匹配，是动态规划的经典题型。在理解本题的过程中，可以形成动态规划的思维。本文将遵循我改进算法的思路，提供四种解题方法，在效率上逐渐提高。本文将通过Java实现，其他语言也很容易改写。

题目如下：

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

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

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

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

链接：https://leetcode-cn.com/problems/regular-expression-matching

一、递归法

递归是最先能想到的思路。既然是字符串匹配，那匹配成功的部分就可以不再去管，转而对s和p的剩下部分进行匹配。递归程序的Java实现如下：

    public boolean isMatch1(String s, String p) {
        if(p.isEmpty())
            return s.isEmpty();

        boolean firstMatch = (!s.isEmpty()) &&
                (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');

        if (p.length() > 1 && p.charAt(1) == '*')
            return firstMatch && isMatch1(s.substring(1), p) || isMatch1(s, p.substring(2));
        else
            return firstMatch && isMatch1(s.substring(1), p.substring(1));
    }

二、改进的递归

在第一种方法中，需要对字符串不断切分，效率很低。不妨通过传递索引加以避免。因此有了递归的改进版本：

    /**
     * @param i: p子串的起点
     * @param j: s子串的起点
     * @return
     */
    public boolean is_match2(int i, int j, String s, String p){
        if(i == p.length())
            return j == s.length();

        boolean firstMatch = (j < s.length()) &&
                (p.charAt(i) == s.charAt(j) || p.charAt(i) == '.');

        if(p.length()-i > 1 && p.charAt(i+1) == '*')
            return firstMatch && is_match2(i,j+1,s,p) || is_match2(i+2, j, s, p);
        else
            return firstMatch && is_match2(i+1, j+1, s, p);
    }

    public boolean isMatch2(String s, String p){
        return is_match2(0, 0, s, p);
    }

三、动态规划

方法二虽然解决了字符串切分的效率问题，但不难发现，仍存在重复计算的问题，因此可以通过动态规划，从后向前算，并将答案存储起来，避免重复的计算。

public boolean isMatch3(String s, String p){
        //dp[i][j]存储s[i:]能否与p[j:]匹配
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];

        for (int i = p.length(); i >= 0; i--) {
            for (int j = s.length(); j >= 0; j--) {
                if(i == p.length())
                {
                    dp[j][i] = j == s.length();
                } else {
                    boolean firstMatch = (j < s.length()) &&
                            (p.charAt(i) == s.charAt(j) ||p.charAt(i) == '.');

                    if(p.charAt(i) == '*' && p.length()>i)
                        dp[j][i] = dp[j][i+1];
                    else if(p.length()-i > 1 && p.charAt(i+1) == '*')
                        dp[j][i] = firstMatch && dp[j+1][i] || dp[j][i+1];
                    else
                        dp[j][i] = firstMatch && dp[j+1][i+1];
                }
            }
        }

这里要注意一点，当p子串以'*'开头时，要单独讨论一下，容易分析出来，这时等价于去掉'*'（这样才能保证后续的判断正确）。

if(p.charAt(i) == '*' && p.length()>i)
  dp[j][i] = dp[j][i+1];

四、正向存储

方法三利用DP从后往前存储，避免重复计算，但实际上也有问题，有些子串的判断其实有多余。因为我们在做递归正向匹配的时候，很多子串并不需要进行匹配。

动态规划的思想其实很简单，不过就是将可能出现的重复特征提取出来，并存储起来。那何必拘泥于从后往前算呢？

因此方法四直接在方法二的基础上，加上一个数组用以存储已经算过的情况，每次递归时，判断一下是否算过即可：

    boolean[][] flag;
    boolean[][] dp;

    /**
     * @param i: p子串的起点
     * @param j: s子串的起点
     * @return
     */
    public boolean is_match4(int i, int j, String s, String p){
        if (flag[j][i]) {
            return dp[j][i];
        }

        if(i == p.length()) {
            dp[j][i] = j == s.length();
        } else{
            boolean firstMatch = (j < s.length()) &&
                    (p.charAt(i) == s.charAt(j) || p.charAt(i) == '.');

            if(p.length()-i > 1 && p.charAt(i+1) == '*') {
                dp[j][i] = firstMatch && is_match4(i,j+1,s,p) || is_match4(i+2, j, s, p);
            } else {
                dp[j][i] = firstMatch && is_match4(i+1, j+1, s, p);
            }
        }
        flag[j][i] = true;
        return dp[j][i];
    }

    //结合isMatch2和isMatch3的方法，
    //需要什么值就算什么，并存储，效率最高
    public boolean isMatch4(String s, String p){
        dp = new boolean[s.length()+1][p.length()+1];
        flag = new boolean[s.length()+1][p.length()+1];
        return is_match4(0, 0, s, p);
    }

抓住动态规划的思想：用存储的方式避免重复讨论，就不必拘于形式。