轉(zhuǎn)載請注明出處：
http://egoistk21.xyz/2016/09/23/Longest Palindromic Substring/

最長回文字符子串

給定一個字符串S，找出S中最長的回文字符子串。

一開始我想用遞歸，現(xiàn)檢驗整個字符串longestPalindrome(String s)，若非回文字，則調(diào)用自身，傳入s.subString(1, s.length)和s.subString(0, s.length - 1)，即不斷的左減一，右減一，檢驗其子串是否回文字。但是我想不好怎么接收return值，所以就用了很水的方法來檢驗，即對于遍歷的每一個字符，檢查其左右是否為回文字，這樣的回文字判斷也分奇數(shù)長度的和偶數(shù)長度的，如“121”和“1221”。具體實現(xiàn)代碼如下：

public static String longestPalindrome(String s) {
    if (s.length() < 2) return s;
    String longerPalindrome = "";
    int length = s.length(), i, j, k;
    for (i = 1; i < length; i++) {
        if (s.charAt(i - 1)==s.charAt(i)) {
            j = i - 1;
            k = i;
            while (j >= 0&&k < length) {
                if (s.charAt(j) == s.charAt(k)) {
                    j--;
                    k++;
                } else {
                    break;
                }
            }
            if ((k - j - 1) > longerPalindrome.length()) {
                longerPalindrome = s.substring(j + 1, k);
            }
        }
        if (i < length - 1&&s.charAt(i - 1)==s.charAt(i + 1)) {
            j = i - 1;
            k = i + 1;
            while (j >= 0&&k < length) {
                if (s.charAt(j) == s.charAt(k)) {
                    j--;
                    k++;
                } else {
                    break;
                }
            }
            if ((k - j - 1) > longerPalindrome.length()) {
                longerPalindrome = s.substring(j + 1, k);
            }
        }
    }
    return longerPalindrome;
}

這樣的方法竟然給水過了，我想去學(xué)習(xí)一下字符串匹配的KMP算法，以后有機會在博客中分享。