題目出處
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 <mark> p or p </mark> "."
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
算法說明
- 此題有類似題，但這題判斷更難寫，可參考：
https://wongwongnotes-github-io.pages.dev/python/leetcode-python-44/
超難的配對問題，比上面那題還更難，首先我們先不管加速，嘗試先寫一個能解的版本
基本版的寫完後，就會發現能 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
見上述說明