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

本題要求實現(xiàn)一個簡單的正則匹配，是動態(tài)規(guī)劃的經(jīng)典題型。在理解本題的過程中，可以形成動態(tài)規(guī)劃的思維。本文將遵循我改進算法的思路，提供四種解題方法，在效率上逐漸提高。本文將通過Java實現(xiàn)，其他語言也很容易改寫。

題目如下：

給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達式匹配。

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

說明:

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

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串。
示例 2:

輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次。

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

一、遞歸法

遞歸是最先能想到的思路。既然是字符串匹配，那匹配成功的部分就可以不再去管，轉(zhuǎn)而對s和p的剩下部分進行匹配。遞歸程序的Java實現(xiàn)如下：

    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);
    }

三、動態(tài)規(guī)劃

方法二雖然解決了字符串切分的效率問題，但不難發(fā)現(xiàn)，仍存在重復(fù)計算的問題，因此可以通過動態(tài)規(guī)劃，從后向前算，并將答案存儲起來，避免重復(fù)的計算。

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];
                }
            }
        }

這里要注意一點，當(dāng)p子串以'*'開頭時，要單獨討論一下，容易分析出來，這時等價于去掉'*'（這樣才能保證后續(xù)的判斷正確）。

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

四、正向存儲

方法三利用DP從后往前存儲，避免重復(fù)計算，但實際上也有問題，有些子串的判斷其實有多余。因為我們在做遞歸正向匹配的時候，很多子串并不需要進行匹配。

動態(tài)規(guī)劃的思想其實很簡單，不過就是將可能出現(xiàn)的重復(fù)特征提取出來，并存儲起來。那何必拘泥于從后往前算呢？

因此方法四直接在方法二的基礎(chǔ)上，加上一個數(shù)組用以存儲已經(jīng)算過的情況，每次遞歸時，判斷一下是否算過即可：

    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];
    }

    //結(jié)合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);
    }

抓住動態(tài)規(guī)劃的思想：用存儲的方式避免重復(fù)討論，就不必拘于形式。