題目10：正則表達(dá)式匹配

給你一個(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

分析

這題可以用回溯方法做，也可以用動(dòng)態(tài)規(guī)劃方法做，因?yàn)樽罱荚谒⒒厮蓊愋偷念}，所以這里只會(huì)使用回溯方法，就是從左到右檢查字符串s能否匹配模式串p的每一個(gè)字符，當(dāng)模式串p中有星號(hào)時(shí)候，星號(hào)前面一定會(huì)有一個(gè)字符，所以這里會(huì)判斷p和s的第一個(gè)字符是否相同，如果相同則將p和s的第一個(gè)字符去掉繼續(xù)匹配，但這里有星號(hào)問題，需要特殊處理，判段p串的第二個(gè)字符是否為星號(hào)，如果為星號(hào)，星號(hào)可以表示字符個(gè)數(shù)為0，可以去掉p的前兩個(gè)字符繼續(xù)匹配，如果s和p第一個(gè)字符都相同，也可以去掉s的第一個(gè)字符繼續(xù)匹配，具體見代碼：

代碼

class Solution {public:    bool isMatch(string s, string p) {        if (p.empty()) return s.empty();        if (p.size() > 1 && p[1] == '*') {            return (isMatch(s, p.substr(2)) || (FirstMatch(s, p) && isMatch(s.substr(1), p)));        } else if (FirstMatch(s, p)) {            return isMatch(s.substr(1), p.substr(1));        }        return false;    }
    bool FirstMatch(string &s, string &p) {        return !s.empty() && (s[0] == p[0] || p[0] == '.');    }};