[LeetCode] Shortest Palindrome 最短回文串

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given <code>"aacecaaa"</code>, return <code>"aaacecaaa"</code>.

Given <code>"abcd"</code>, return <code>"dcbabcd"</code>.

Credits:

C++ 解法一：

Java 解法一：

從上面的Java和C++的代碼中，我們可以看出來C++和Java在使用雙等号上的明顯的不同，感覺Java對于雙等号對使用更加苛刻一些，比如Java中的雙等号隻對primitive類資料結構(比如int, char等)有效，但是即便有效，也不能将結果直接當1或者0來用。而對于一些從Object派生出來的類，比如Integer或者String等，不能直接用雙等号來比較，而是要用其自帶的equals()函數來比較，因為雙等号判斷的是不是同一個對象，而不是他們所表示的值是否相同。同樣需要注意的是，Stack的peek()函數取出的也是對象，不能直接和另一個Stack的peek()取出的對象直接雙等，而是使用equals或者先将其中一個強行轉換成primitive類，再和另一個強行比較。

下面這種方法的寫法比較簡潔，雖然不是明顯的KMP算法，但是也有其的影子在裡面，首先我們還是先将其的翻轉字元串搞出來，然後比較原字元串s的字首後翻轉字元串t的對應位置的字尾是否相等，起始位置是比較s和t是否相等，如果相等，說明s本身就是回文串，不用添加任何字元，直接傳回即可；如果不想等，s去掉最後一位，t去掉第一位，繼續比較，以此類推直至有相等，或者循環結束，這樣我們就能将兩個字元串在正确的位置拼接起來了。很有意思的是，這種方法對應Java寫法卻會TLE，無法通過OJ。

C++ 解法二：

下面這種Java寫法也是在找相同的字首字尾，但是并沒有每次把字首字尾取出來比較，而是用兩個指針分别指向對應的位置比較，然後用end指向相同字尾的起始位置，最後再根據end的值來拼接兩個字元串。有意思的是這種方法對應的C++寫法會TLE，跟上面正好相反，那麼我們是否能得出Java的substring操作略慢，而C++的reverse略慢呢，我也僅僅是猜測而已。

Java 解法三：