想到正則表達式，如果能夠 import re，那絕對相當地快速。用 re 的函式就不需要去寫判斷了。
今天拋棄 re，這題限制居多，輸入字串不能局部配對，一定要全部吻合。難度會比真的re運作還簡單不少。
在我心目中，不能只是解題，還要符合 re 的運作模式，才是我要的解法。
但還是先解題優先吧。
首先有 si 跟 pi，代表兩個字串的索引，兩者都從 0 找起，如果 si 到底(等於s長度)，而且也 pi 到底，代表 s 跟 p 全部匹配。
說到特殊符號，"."相對容易處理，這裡就不提了，不過"*"就困難一些，"*"代表前面字符可以出現 0或1次或1次以上，因此產生了許多可能性。
由於"*"僅影響前面的字符，所以當我們在匹配 s[si] 與 p[pi] 時，要考慮 p[pi+1]是否為"*"，同時也要小心是否 pi+1 超出邊界，以免p[pi+1]報錯。
當後面是"*"時，匹配有三種變化，分別對應 0 或 1次 或 1次以上 的情形
第一種出現0次，si保持不到，而pi直接+2跳過"*"，繼續遞迴下去。
第二種出現1次，若有匹配到，si+1 pi+1，往深遞迴。
第三種出現多次，若有匹配到，si+1 pi不變，往深遞迴。
由於"*"使得可能性開枝散葉變多，而造成重複計算，而且每組 si pi都只會有一種結果，因此可以使用dp去減少計算時間。(這裡使用lru_cache)
這讓我更了解dp的使用時機：會重複計算，而且相同參數只有會一種結果。
接下來要考慮例外，如果 (s,p) = ("","")、("",".*")、("a","")、("","b")，這些情況下能順利解決？
這裡先看到 si == len(s)，搜尋到了底，這時要提防 p 是否還有長度可以搜尋，如果剩下".*"要如何解決。
當 si == len(s)，代表只剩 "" 可以拿來比較，如果剩餘的p可以匹配""字串，那代表兩者相同。
而p能匹配空字串的，只有p[pi]後面是"*"。
空字串只會匹配後面有"*"的第一種情形，於是pi+2。如果剛好是".*"也能匹配到，但匹配到的結果會使 si +1 而往下會使得 si > len(s)，超出範圍就不用匹配。
這樣子寫，也不需要在開頭做例外處理。
class Solution:
def isMatch(self, s: str, p: str) -> bool:
from functools import lru_cache
n, n2 = len(s), len(p)
self.res = False
@lru_cache(None)
def nextMatch(si, pi):
if si > n or pi >= n2:
if si == n and pi == n2: self.res = True
return False
elif si == n:
c = ""
else:
c = s[si]
#
ch = p[pi]
# 如果後面是 "*" 字，分別採取不同搜尋
if pi+1 < n2 and p[pi+1] == "*":
if c == ch or ch == ".":
nextMatch(si+1, pi) # 原地不動
nextMatch(si+1, pi+2) # 或向前走
nextMatch(si, pi+2) # 當作沒有配對到
else:
# 後面沒有 *
if c == ch or ch == ".":
nextMatch(si+1, pi+1)
nextMatch(0, 0)
return self.res