難度: Hard
類型: String, Dynamic Programming, Greedy, Recursion
CPP程式下載: 44.cpp
前情題要:
含任意字元 '?' 與 '*' 的 pattern match。
思考方式:
1. '*' 是一個特殊的存在, 可以代表任意字串, 也可以是空字串。'?' 則是任意一個字元, 不能為空字串。
2. 首先, 先尋找 '*' 在 pattern 字串中有幾個。若是沒有, 那就是字串 s 和 p 要完全match。若是只有一個 '*', 就把 p 字串分成 '*' 前, 以及 '*' 後兩個字串, 前字串與 s 字串從前面開始比對, 後字串從 s 字串最後方開始往前比對, 若都能 match 且 s 字串中間還有其他字元, 或是剛剛好沒有其他字元, 那麼就是 pattern match。
3. 若 '*' 在 p 字串中有兩個以上, 就把 p 字串切成三份, 第一個 '*' 前, 最後一個 '*' 後, 以及中間含 n-2 個 '*' 的字串。一樣前後字串各自從前後單獨比對。然後中間的字串每兩個 '*' 夾在中間的的字元順序與個數, s 的中間字串要和 p 的中間字串彼此字元順序要相同, 長度相同, 但可以在 s 字串中間隔幾個任意字元組合後再相同。
複雜度思考:
Time Complexity: O( (n-2)*strlen(s) )
Space Complexity: O( x )
結果:
Runtime: 3 ms, Beats: 96.32%
Memory: 12.97 MB, Beats: 83.03%
