題目：
給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p，請(qǐng)你來實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配。

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

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

示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "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

方法一：遞歸回溯
思路：
1、比較s的第一個(gè)字母與p的第一個(gè)字母是否相同
2、判斷p第二個(gè)字母是否為'*'，如果是，分兩種情況
（1）#*匹配0個(gè)字符
（2）刪除匹配串的第一個(gè)字符，前提是它能夠匹配模式串當(dāng)前位置字符
3、如果p第二個(gè)字母不為'*'，比較s[i] === s[j] && s[:1] === p[:1]

var isMatch = function(s, p) {
    if(p === '')
        return s === ''
    let firstMatch = s !== '' && (s[0] === p[0] || p[0] === '.');
    // 當(dāng)長度大于2的時(shí)候，才考慮 *
    // ---兩種情況
    //p 直接跳過兩個(gè)字符，表示  * 前邊的字符出現(xiàn) 0 次
    //p 不變，接著用第一個(gè)字符和前面比較，表示 * 用前一個(gè)字符替代 【s = aa , p = a*】
    if(p.length >= 2 && p[1] === '*')
        res = isMatch(s, p.substring(2)) || firstMatch && isMatch(s.substring(1), p)
    else 
        res = firstMatch && isMatch(s.substring(1), p.substring(1))
    return res;
};

方法二：動(dòng)態(tài)規(guī)劃
思路參考：
https://leetcode-cn.com/problems/regular-expression-matching/solution/dong-tai-gui-hua-zen-yao-cong-0kai-shi-si-kao-da-b/

var isMatch = function(s, p) {
    let len_s = s.length;
    let len_p = p.length;

    let dp = Array.from(new Array(len_s + 1), () => new Array(len_p + 1).fill(false))
    dp[0][0] = true;
    for(let i = 1; i < len_p; i++){
        if(p[i] === '*')
            dp[0][i + 1] = dp[0][i - 1]
    }
    for(let i = 0; i < len_s; i++){
        for(let j = 0; j < len_p; j++){
            if(s[i] === p[j] || p[j] === '.')
                dp[i + 1][j + 1] = dp[i][j]
            else if(p[j] === '*'){
                if(s[i] !== p[j - 1] && p[j - 1] !== '.'){
                    dp[i + 1][j + 1] = dp[i + 1][j - 1]
                }else{
                    dp[i + 1][j + 1] = dp[i + 1][j] || dp[i + 1][j - 1] || dp[i][j + 1]
                }
            }
        }
    }
    return dp[len_s][len_p]
};