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

示例1

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

示例2

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

提示

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

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

以示例2為例講解：

• 初始化取 dp[0][0] = true，代表匹配成功；
• 當(dāng)s取“a”的時(shí)候：p取“a”時(shí)候，成功；
• p取“ab”的時(shí)候，失敗；
• p取“ab*”時(shí)候，*出現(xiàn) 0 次，即為 p 取 “a” 時(shí)候，成功；
• p取“ab*.”的時(shí)候，失敗，因?yàn)?s 只有一個(gè)字母，“.” 可以是任意字母，不滿足；
• p取“ab*.*”的時(shí)候，“.” 出現(xiàn) 0 次，“b”出現(xiàn) 0 次，成功。
• 以此類推……

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(MN)，其中 M,N 分別為 s 和 p 的長(zhǎng)度，狀態(tài)轉(zhuǎn)移需遍歷整個(gè) dp 矩陣。
• 空間復(fù)雜度：O(MN)，狀態(tài)矩陣 dp 使用 O(MN) 的額外空間。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！