Leetcode

LeetCode: Regular Expression Matching

題目類型:找出能用pattern表示的string,可以表示回傳true,使用動態規劃解析問題

. → 任何字母都可以

* → 前面的字母可以乘幾次

// Case 1: 演示一般case 
s = "aa"
p = "a"
// Case 2: 演示乘法的case
s = "aaaa"
p = "a*b*"
// Case 3: 演示混合的狀況
s = "mississippi"
p = "mis*is*p*."
解題規則

pattern 沒有遇到 * ,只要 s[i-1] 與 p[j-1] 一樣,或是 p[j-1] 為 . 那dp[j][i] = 1

pattern 遇到 * , 則檢查如果dp[j-2][i] 為 1,則dp[j][i] = 1 (0倍狀態)

pattern 遇到 * ,檢查如果 (p[j-2] == s[i-1] 或是 p[j-2] == ‘.’ ) 且 dp[j][i-1] 也為 1 (前一個倍數為True)

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *