難度: Hard
類型: String, Dynamic Programming, Recursion
前情題要:
一個 source string, 一個 pattern string, 規則如下:
'．': 代表任一字元
'＊': 代表 0個到多個前一個字元。
如果 source string 可以符合 pattern string 的規則, 就回傳 true, 反之則回傳 false。
思考方式:
1. 這邊的’＊’, 與原本認知的"0個到多個任意符號", 並不相同。注意, 是"0個到多個的前一個符號"。譬如 "r*", 就是0到多個r。譬如 ".*" 才是0到多個任意符號。如果這邊沒有注意到, 會多走很多冤枉路。
2. 10_1.cpp 跟 10_2.cpp, 是不同時間寫出來的, 基本上 10_1.cpp 好一點點。10_2.cpp 是先找到 '*' 再回推, 所以計算上會稍稍多走一點冤枉路。不過差不太多, 10_1.cpp 最快花費869ms, 空間約10.2MB; 10_2.cpp 最快花費963ms, 空間約9.4MB。
3. 後來我發現 "isMatch(s.substr(j), p.substr(i+1))" 上。首先 substr 是會複製一個 string 出來, 而 isMatch 的輸入string, 是傳 string 實體, 而不是傳位置, 這代表每次 recursion 呼叫一次, 就複製一個新的 string 然後進到函數前再被複製一次。然而很多次 recursion 的呼叫累積下來, 浪費了很多時間。這邊要改。
4. 10_3.cpp 就是改了recusion 呼叫的函數, 改成傳 array pointer。很明顯的, 從結果來看, 時間上的花費從 869~1100ms 降到了526~550ms, 而空間上的花費從9.4MB降到了7.9MB~8.1MB。
5. 10_4.cpp, 與10_3.cpp相比則是優化了流程, 一邊找 '*' 的同時, 也一邊比較第 i-1或i-2 位置之前的char* p 與 char* s。這邊可以看到時間上優化有限, 進步到507~519ms, 而空間上沒差別, 也是 7.9MB~8.1MB。
到這邊先告一段落, 再來進步有限。有更好的方法歡迎留言討論~
複雜度思考:
Time: O ( N! )
Memory: O ((M+N+2)*sizeof(char))
結果:
636 / 636 testcases passed
Runtime: 507 ms, Beats: 7.43%
Memory: 7.92 MB, Beats: 94.83%
