LeetCode 筆記 - 10. Regular Expression Matching
題目在此 10. Regular Expression Matching
給定一個字串 s 與一個模式字串 p,請實作一個函式來判斷 s 是否符合 p 的模式。模式字串 p 可以包含以下兩種特殊字元:
.:匹配任意單一字元。*:匹配零個或多個前一個字元。
例如:
s = "aa",p = "a",會回傳false,因為a無法匹配整個字串aa。s = "aa",p = "a*",會回傳true,因為a*可以匹配aa(a出現兩次)。s = "ab",p = ".*",會回傳true,因為.*可以匹配任意字串。
解題思維
這題的關鍵在於理解 * 的行為。* 可以匹配零個或多個前一個字元,這意味著我們有兩種主要情況需要考慮:
*匹配零次:這種情況下,我們可以忽略*及其前一個字元,繼續匹配剩餘的字串和模式。*匹配一次或多次:這種情況下,我們需要確保*前的字元與當前字串的字元匹配,然後繼續匹配字串的下一個字元與模式。- 如果模式字串的下一個字元不是
*,那麼我們只需要確保當前字元匹配,然後繼續匹配下一個字元。
first_match 變數用來檢查當前字元是否匹配,這包括直接匹配或通過 . 匹配。
為了避免重複計算,我們可以使用記憶化遞迴(memoization)來存儲已經計算過的子問題結果。
如果 p[1] == '*',我們有兩種選擇:
- 忽略
*和它前面的字元,繼續匹配s和p[2:]。 - 如果
first_match為真,則我們可以讓*匹配當前字元,並繼續匹配s[1:]和p。
如果p[1]不是*,我們只需確保當前字元匹配,然後繼續匹配s[1:]和p[1:]。
程式碼
1 | class Solution: |