【Leetcode】python – [10] Regular Expression Matching 個人解法筆記

➣ Reading Time: 13 minutes

題目出處

10. Regular Expression Matching

難度

hard

個人範例程式碼

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        self.memo = {}
        return self.dfs(s, p, 0, 0)

    def dfs(self, s, p, start_s, start_p):
        # print(start_s, start_p)
        if (start_s, start_p) in self.memo:
            return self.memo[(start_s, start_p)]

        # end of recursion
        if len(s) <= start_s and len(p) <= start_p:
            return True
        if len(s) > start_s and len(p) <= start_p: # s left
            return False
        if len(s) <= start_s and len(p) > start_p: # p left # must be a* case
            return self.is_empty(p[start_p:])

        if start_p+1 < len(p) and p[start_p+1] == "*":
            # if * means nothing, self.dfs(s, p, start_s, start_p+2) # skip a*
            # if * means duplicate, self.dfs(s, p, start_s+1, start_p) # keep a*, if s[i] == p[i]
            ans = (self.is_char_matched(s[start_s], p[start_p]) and self.dfs(s, p, start_s+1, start_p)) or self.dfs(s, p, start_s, start_p+2) 
        elif self.is_char_matched(s[start_s], p[start_p]):
            ans = self.dfs(s, p, start_s+1, start_p+1)
        else:
            ans = False

        self.memo[(start_s, start_p)] = ans
        return ans

    def is_char_matched(self, s, p):
        return s == p or p == "."

    def is_empty(self, p):
        for idx in range(1, len(p), 2):
            if p[idx] == "*":             
                continue
            else:
                return False
        return True if p[-1] == "*" else False

算法說明

  • 此題有類似題,但這題判斷更難寫,可參考:

【Leetcode】python – [44] Wildcard Matching 個人解法筆記

超難的配對問題,比上面那題還更難,首先我們先不管加速,嘗試先寫一個能解的版本

基本版的寫完後,就會發現能 pass,但超慢,
原因是因為我們的搜索時間是「指數等級」的,看來是要稍微優化一下。

比上面那題佛心了… 上面那題還會 TLE,但可能這題更難寫條件式的關係

判斷的先後順序

這裡的 * 沒有像上一題那麼萬用,他必須要搭配合理的「前綴字」才能發揮效力。

在處理上,我們需要先判斷「i+1」是否為
免得我們一個衝動讓 「c
!= a」,return False 就糗大了

* 的處理

一樣也是分兩路

  • 如果 * 代表的是沒有東西,則判斷 self.dfs(s, p, start_s, start_p+2)
  • 如果 * 代表的是重複的東西,則判斷 self.dfs(s, p, start_s+1, start_p)

但注意!!!! 這裡還有一個陷阱!!!
我們需要多保證 s[i] p[i],不能直接寫,
否則在碰到 cab 與 aab 這種 case ,就會出錯了。(被 c* 干擾了,c 沒有重複)

因此整理之後得到

  • 如果 * 代表的是沒有東西,則判斷 self.dfs(s, p, start_s, start_p+2)
  • 如果 * 代表的是重複的東西,則判斷 self.is_char_matched(s[start_s], p[start_p]) and self.dfs(s, p, start_s+1, start_p)

結束條件

分成三種:

  • 如果 start_s, start_p 同時 >= len(s), len(p),屬正常情況 return True
  • 只有 start_p >= len(p),表示有剩餘 s,return False
  • 只有 start_s >= len(s),表示有剩餘 p,要特別處理

我們要判斷 p 是否可以代表 “”,

我們在上述切割時,有遇到 * 都是保留「a」的情況進行切割,
因此 p[0] = “
” 的情況不會單獨出現 (除非 input 有問題),任何「a*」一定會被完整的切割掉

最後要多判斷一個 [-1] “*”,確保尾巴沒有殘留的東西 (因為 range 2 有可能會漏掉一個)

def is_empty(self, p):
    for idx in range(1, len(p), 2):
        if p[idx]  "*":             
            continue
        else:
            return False
    return True if p[-1]  "*" else False

記憶化搜索 (DP)

我們用一個策略紀錄我們搜尋的結果,主要因為我們進行的「重複搜尋」太多了,
我們透過記憶 start_p, start_q 的兩個起始位置,與對應結果。

當遞迴再一次回到此位置時,直接去 hashtable 拿 (start_p, start_q) 的結果來用。

這邊我們強調一下增加的部分:

  • 拿取
if (start_s, start_p) in self.memo_matched_begin:
    return self.memo_matched_begin[(start_s, start_p)]
  • 儲存
self.memo_matched_begin[(start_s, start_p)] = ans

這個就是一種「以空間換取時間」的策略

於是我們就能完成這道 hard 的題目。

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

input handling

x

Boundary conditions

見上述說明

Reference

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 693

★留個言吧!內容有誤或想要補充也歡迎與我討論!