palindrome 迴文判斷兩方向

初次解 LeetCode 的 5. Longest Palindromic Substring ，沒有想太多，把迴文的判斷一個個用上，有更長的就取代掉舊的，結果沒有 time out 但成果非常不滿意，耗時 1966ms ，只快過 5.01% 的投稿，記憶體耗 39.7 MB，只少於 41.33% 的投稿。不得不思考有沒有別的方法。原本我在過去幾題迴文的判斷，是因為已經知道字串的起點與終點，所以我是「由外而內包夾」，如下：

在這題的想法是這樣的，先讓 i 由 index = 1 到 index = 全長 - 2，（選擇 1 開始是因為當整個字串不存在任何迴文部份時，s.charAt(0) 至少是一個單獨迴文且最長的字串，全長 - 2 是保留往後探訪的空間），例如上圖 i = 1 ，再往後一層 j for loop，j 從最後也就是右邊，逐一往左愈來愈小，形成一個「包夾」檢查是否迴文，所以下一個檢查 index = 1+1 和 index = 5-1，接著是 1+2 和 5-2 ，當兩個指標相等或左右順序相反則跳出 while ，這樣的迴文字串夠長的話就賦值給 result ，全部跑完則 return 。

雖然有加入一些判斷例如 i 太大（接近右邊尾聲）如果已經得到的迴文長度 max 也夠大，即使再找出新的迴文恐怕長度也不長就沒有意義，所以 i + max > s.length() 就結束，但還是耗費相當大的時間。

考慮到由外而內包夾的方法，可能在外層有前後對應，但是靠向中間一旦沒迴文的對稱時，那之前的步驟都付諸流水，不如把迴文的判斷「由內向外」試試看，不過這又牽扯迴文的字數是奇數還是偶數，奇數如 ABCBA、0987890，而偶數如ABCCBA、12344321：

奇數時：

例如上圖 i = 3，檢查前一個和後一個也就是 index = 2 和 index = 4，有相同時開始做迴文檢查，逐步往外 index = 1 和 index = 5，直到不再對稱，長度夠長就賦值給 result。

偶數時：

例如上圖 i = 3，檢查下一個 i = 4 是否相等，是就開始做迴文檢查逐步往外 index = 2 和 index = 5，是再繼續 index = 1 和 index = 6，直到不再對稱。

這樣做的表現非常的好，投稿後耗時 14ms，快過 95.87% 的投稿，記憶體耗 38.7 MB，少於 93.51% 的投稿。其實本來覺得差距不大，但仔細去思考複雜度，原本由外而內的包夾作法 i 先遍尋 n，然後 j 從後往前遍尋 n - i，再包夾遍尋 ( j - i ) / 2 。而由內而外拓展作法，是 i 遍尋 n，每次向外 (n - i) / 2 和 i / 2 之較小值，難怪效率差這麼多，很有意思的發現。