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

示例1

• 輸入: s = "aa"，p = "a"

• 輸出: false

• 解釋: "a" 無法匹配 "aa" 整個字符串。

示例2

• 輸入: s = "aaa"，p = "ab*.*"

• 輸出: true

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

提示

• s 可能為空，且只包含從 a-z 的小寫字母。

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

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

以示例2為例講解：

• 初始化取 dp[0][0] = true，代表匹配成功；

• 當(dāng)s取“a”的時候：p取“a”時候，成功；

• p取“ab”的時候，失??；

• p取“ab*”時候，*出現(xiàn) 0 次，即為 p 取 “a” 時候，成功；

• p取“ab*.”的時候，失敗，因?yàn)?s 只有一個字母，“.” 可以是任意字母，不滿足；

• p取“ab*.*”的時候，“.” 出現(xiàn) 0 次，“b”出現(xiàn) 0 次，成功。

• 以此類推……

代碼如下：

復(fù)雜度分析

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

• 空間復(fù)雜度：O(MN)，狀態(tài)矩陣 dp 使用 O(MN) 的額外空間。

END

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

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。