LeetCode 筆記 - 10. Regular Expression Matching

Posted on

題目在此 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，因為 .* 可以匹配任意字串。

解題思維

這題的關鍵在於理解 * 的行為。* 可以匹配零個或多個前一個字元，這意味著我們有兩種主要情況需要考慮：

  1. * 匹配零次：這種情況下，我們可以忽略 * 及其前一個字元，繼續匹配剩餘的字串和模式。
  2. * 匹配一次或多次：這種情況下，我們需要確保 * 前的字元與當前字串的字元匹配，然後繼續匹配字串的下一個字元與模式。
  3. 如果模式字串的下一個字元不是 *，那麼我們只需要確保當前字元匹配，然後繼續匹配下一個字元。

first_match 變數用來檢查當前字元是否匹配，這包括直接匹配或通過 . 匹配。
為了避免重複計算，我們可以使用記憶化遞迴（memoization）來存儲已經計算過的子問題結果。

如果 p[1] == '*'，我們有兩種選擇：

  • 忽略 * 和它前面的字元，繼續匹配 s 和 p[2:]。
  • 如果 first_match 為真，則我們可以讓 * 匹配當前字元，並繼續匹配 s[1:] 和 p。
    如果 p[1] 不是 *，我們只需確保當前字元匹配，然後繼續匹配 s[1:] 和 p[1:]。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    @cache
    def isMatch(self, s: str, p: str) -> bool:

        if not p:
            return not s

        first_match = bool(s) and (p[0] == s[0] or p[0] == '.')

        if len(p) >= 2 and p[1] == '*':

            return (
                # * match 0 time
                self.isMatch(s, p[2:]) or
                # * match 1 or more times
                first_match and self.isMatch(s[1:], p)
            )
        else:
            # match one by one
            return first_match and self.isMatch(s[1:], p[1:])

也許你也會想看看