這是LeetCode上面一道難度為困難的題目，記錄一下，整的來說，遞歸方法描述起來思路清晰，動(dòng)態(tài)規(guī)劃描述需要借用一定的圖畫或者表格手段。

正則表達(dá)式匹配

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來匹配包含'. '和''的正則表達(dá)式。模式中的字符'.'表示任意一個(gè)字符，而''表示它前面的字符可以出現(xiàn)任意次（含0次）。在本題中，匹配是指字符串的所有字符匹配整個(gè)模式。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但與"aa.a"和"ab*a"均不匹配。

示例 1:

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無(wú)法匹配 "aa" 整個(gè)字符串。

示例 2:

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

示例 3:

輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個(gè)或多個(gè)（'*'）任意字符（'.'）。

示例 4:

輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因?yàn)?'*' 表示零個(gè)或多個(gè)，這里 'c' 為 0 個(gè), 'a' 被重復(fù)一次。因此可以匹配字符串 "aab"。

示例 5:

輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false

s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母以及字符 . 和 *，無(wú)連續(xù)的 '*'。

遞歸解法：

    public boolean isMatch(String t, String p) {
        // 遞歸的邊界值，當(dāng)t的長(zhǎng)度為0的時(shí)候
        if (t.length()==0) {
            // p必須是（字符+*）的結(jié)構(gòu)，所以長(zhǎng)度需要為偶數(shù)
            if (p.length()%2!=0) return false;
            // 查找*號(hào)，如果有單獨(dú)的字符，立刻返回false
            for (int i = 0; i < p.length(); i+=2) {
                if (p.charAt(i)!='*') {
                    return false;
                }
            }
            return true;
        }
        // 當(dāng)p為""的時(shí)候返回false
        if (p.length()==0) {
            return false;
        }
        // 獲取t和p第一位
        char t0 = t.charAt(0),p0 = p.charAt(0),p1 = 0;
        // p1為p的第二位
        if (p.length()>1) {
            p1 = p.charAt(1);
        }
        
        // 如果p1不為*號(hào)，則當(dāng)前位必須匹配
        if (p1!='*') {
            // t0==p0或者p0為'.'，當(dāng)前位置匹配成功，匹配后續(xù)
            if (t0==p0||p0=='.') {
                return isMatch(t.substring(1),p.substring(1));
            } else {
                return false;
            }
        } else {
            // p1為*號(hào)，則存在兩種情況
            // 1.c*為空
            // 2.c*為多個(gè)c
            // 匹配當(dāng)前字段
            if (t0==p0||p0=='.') {
                // 當(dāng)前字段匹配成功，則有兩種情況
                // 1.后續(xù)需要再次匹配
                // 2.跳過c*的匹配
                return isMatch(t.substring(1),p) || isMatch(t,p.substring(2));
            } else {
                // 匹配失敗，嘗試匹配跳過c*的部分
                return isMatch(t,p.substring(2));
            }
        }
    }

動(dòng)態(tài)規(guī)劃解法：

    // 正序解法，從長(zhǎng)度0到長(zhǎng)度n
    public boolean isMatch(String t, String p) {
        int n = t.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        // dp數(shù)組里包含了從長(zhǎng)度為0，到長(zhǎng)度為n,m的所有情況
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 空正則串的情況
                if (j == 0) {
                    // 空正則的情況下，只有t為空字符串的時(shí)候匹配為true
                    dp[i][j] = (i == 0);
                } else {
                    //非空正則分為兩種情況
                    // 長(zhǎng)度為j的正則字符串的最后一個(gè)字符為“*”
                    // 與不為“*”的情況
                    if (p.charAt(j - 1) != '*') {
                        // 當(dāng)前正則串的字符的尾字符不是“*”
                        // 字符床長(zhǎng)度都大于0，且尾字符相等，或者p的尾字符為'.'的時(shí)候，當(dāng)前字符匹配成功，dp[i][j]=dp[i-1][j-1]
                        // 否則匹配失敗使用默認(rèn)的false
                        if (i > 0 && j > 0 && (t.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    } else {
                        // 當(dāng)前正則串的字符的尾字符是“*”
                        // 假設(shè)c*的個(gè)數(shù)為0,則直接忽略正則的兩個(gè)字符
                        if (j >= 2 ) {
                            dp[i][j] = dp[i][j - 2];
                        }
                        // c*匹配多個(gè)字符的時(shí)候
                        // t的長(zhǎng)度必須大于1,否則按照c*為0即可獲得true
                        // 接下來判斷正則字符串p的倒數(shù)第二個(gè)字符和t的尾巴字符是否相等
                        // 或者是否為'.'
                        // 滿足條件，則當(dāng)前字符匹配成功
                        if (i >= 1 && j >= 2 && (t.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                            // 當(dāng)前字符匹配功后，即可忽略t的尾字符串
                            // 即d[i][j] = dp[i-1][j]
                            // 這里或上c*個(gè)數(shù)為0的情況，得到最后結(jié)果
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
            }
        }
        // 返回長(zhǎng)度為n,m的兩個(gè)字符串的匹配結(jié)果
        return dp[n][m];
    }

    // 逆序解法，從最后一個(gè)字符開始匹配
    public boolean isMatch(String t, String p) {
        // 存儲(chǔ)匹配狀態(tài)，默認(rèn)為false
        boolean[][] memo = new boolean[t.length()+1][p.length()+1];
        // 初始化""與""的匹配結(jié)果，為true
        memo[t.length()][p.length()] = true;

        // i代表t的第i位，j代表p的第j位
        // i = t.length 代表 ""
        for (int i = t.length();i>=0;i--) {
            for (int j = p.length() - 1; j >= 0; j--) {
                // 如果t[i]==p[j]或者p[j]=='.' 則認(rèn)為當(dāng)前字符匹配成功
                boolean first = i < t.length() && (t.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                // 如果p[j]后面跟了一個(gè)*號(hào)
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    // 將c*視為0個(gè)的時(shí)候，即當(dāng)前跳過p[j]和p[j+1](c*兩個(gè)字符)匹配t[i]與p[j+2]
                    // 將c*視為多個(gè)的時(shí)候，即視作當(dāng)前字符匹配成功與匹配t[i+1]與p[j]的結(jié)果
                    // （"ab"匹配"a*b",在"b"與"a*b"的匹配中，走了a*為0的條件）
                    // ex : t[aa] p[a*] memo[2][2] = true
                    // ex : t[2] p[2->0] memo[2][1] = false memo[2][0] = true 
                    // ex : t[1] p[2->0] memo[1][2] = false memo[1][1] = false memo[1][0] = true
                    // ex : t[0] p[2->0] memo[0][2] = false memo[0][1] = false memo[0][0] = true
                    memo[i][j] = memo[i][j + 2] || first && memo[i + 1][j];
                } else {
                    // p[j]后面沒有*號(hào)
                    // 判斷當(dāng)前字符是否相等與t[i+1] p[j+1] 匹配結(jié)果
                    memo[i][j] = first && memo[i + 1][j + 1];
                }
            }
        }
        // 返回t[0]和p[0]的比較結(jié)果
        return memo[0][0];
    }