[leetcode][python]44. Wildcard Matching

這題看起來不難，實際上跑了之後才知道原來難在速度

一開始使用遞迴的方式，s與p比較

• 若s/p相同或是p的部分為'?'，則將剩下的部分繼續遞迴處理
• 若p 為'*'，代表match 0~n 個字，則依序比較s[i:]~s[i+n:] 與p[j+1:]
• 這邊有一個訣竅: 連續多個* 可直接當作一個*，可大幅減少計算量

這樣做簡單的Test case可以過，但較長的test case 則會timeout



第二次嘗試加快

• 對p 做預處理，去掉重複的*
• 減少遞迴的成分，使用while loop & s/p 的index 處理，但在'*' 的部分仍繼續使用遞迴處理

這樣仍然相同，較長的test case 則會timeout(但在我自己的pc上面不用10s)

最後第三次嘗試完全不用遞迴，在處理'*' 時，直接存下還原點，若做到失敗時，跳回還原點，s從i+1繼續開始嘗試

• 這邊會有一個疑問:當一個* 正在嘗試處理所有可能時，又遇到下一個*，此時第一個* 暫存點就被覆蓋了
• 不過我們可以反過來想，若是後面還有*(注意第二字嘗試的最佳化已經先移除連續的*了)，且已經跑到判斷第二個* ，就代表兩個*中間夾的字已經出現過第一次，此時無論兩個* 中間夾的字出現過幾次都是等價的
• 例如下面這個例子，無論bb對應到bb 或bb，前後多餘的字都可以被* 吃掉，所以等價，直接從第二個* 之後繼續嘗試即可
• "aattbbtttbbttcc"/"aa*bb*cc"

這次終於可以通過測試了!

leetcode:
https://leetcode.com/problems/wildcard-matching/

src:
https://github.com/cy-arduino/leetcode/blob/master/44.%20Wildcard%20Matching.py