請實現一個函數用來匹配包含'. '和'*'的正則表達式。模式中的字符'.'表示任意一個字符，而'*'表示它前面的字符可以出現任意次（含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
• 解釋: 因為 '*' 表示零個或多個，這里 'b' 為 0 個, '.' 為 a , 重復2次。因此可以匹配字符串 "aaa"。

提示

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

方法：動態規劃

以示例2為例講解：

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

代碼如下：

復雜度分析

• 時間復雜度：O(MN)，其中 M,N 分別為 s 和 p 的長度，狀態轉移需遍歷整個 dp 矩陣。
• 空間復雜度：O(MN)，狀態矩陣 dp 使用 O(MN) 的額外空間。

END

本文內容出處是力扣官網，希望和大家一起刷算法，在后面的路上不變禿但是變強！