難度: Medium
類型: Two Pointers, String, Dynamic Programming
CPP程式下載: 5.cpp
==========================
前情題要:
找最長且左右對稱的子字串
==========================
思考方式:
分成子字串個數是偶數, 以及奇數。
1. 若是奇數, 則每個char (s[i]) 當中心, 他左右的兩個 chars 相同, 就繼續往兩邊擴, 長度從1變3, 從3便5, 以此類推, 只要不相同, 就檢查下一個 s[i+1]。
2. 若是奇數, 那 s[i] 就該跟 s[i+1] 相同, s[i-1] 要跟 s[i+2]相同, 以此類推。
3. 無論 1 或 2. 記得紀錄最長的對稱字串的頭尾 index。回傳最大對稱子字串時拿來用。
==========================
複雜度思考:
Time: O (M*(M-1))
Memory: O (1)
==========================
結果:
Runtime: 7 ms, Beats: 88.75%
Memory: 9.42 MB, Beats: 71.64%
