題目：給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

PS：回文字符串概念：回文是一個(gè)正讀和反讀都相同的字符串。

算法思路：

1. 常規(guī)算法：增加一個(gè)方法判斷給定的字符串是否是回文字符串，以此遍歷字符串的各個(gè)子串，從中查找出最大的回文字符串，時(shí)間復(fù)雜度是 O(n^3)；
2. 中心擴(kuò)展算法：借助回文字符串的定義，可以知道回文串的中心兩側(cè)互為鏡像，因此，回文串的遍歷可以從中心開(kāi)始，并且有 2n - 1 個(gè)這樣的中心，因?yàn)榕紨?shù)長(zhǎng)度的回文串的中心處于兩個(gè)中心字母之間（如“abccba”的中心在兩個(gè)'c'之間）；時(shí)間復(fù)雜度為 O(n^2)，空間復(fù)雜度為 O(1)；

算法代碼：根據(jù)算法思路1，寫(xiě)出的算法具體代碼如下：

    // Java代碼實(shí)現(xiàn)：最長(zhǎng)回文子串
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        int maxLength = 0;
        int maxStart = 0;
        int maxEnd = 0;
        int curLength;
        for(int i = 0; i < len - 1; i ++) {
            for (int j = i + 1; j < len; j ++) {
                if (s.charAt(j) == s.charAt(i)) {
                    if (isPalindrome(s.substring(i, j + 1))) {
                        curLength = j - i + 1;
                        if (curLength > maxLength) {
                            maxLength = curLength;
                            maxStart = i;
                            maxEnd = j;
                        }
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }

    public static boolean isPalindrome(String s) {
        int len = s.length();
        for (int i = 0; i < len /2; i ++) {
            if (s.charAt(i) != s.charAt(len - 1 - i)) {
                return false;
            }
        }
        return true;
    }

算法代碼：根據(jù)算法思路2，寫(xiě)出的算法具體代碼如下：

// Java代碼實(shí)現(xiàn)：最長(zhǎng)回文子串
public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        int maxLength = 0;
        int maxStart = 0;
        int maxEnd = 0;
        for(int i = 0; i < len - 1; i ++) {
            int findLen1 = expandAroundCenter(s, i, i); // 考慮“aba”的情況
            int findLen2 = expandAroundCenter(s, i, i + 1); // 考慮“cbbc”的情況
            int findLen = Math.max(findLen1, findLen2);
            if (findLen > maxLength) {
                maxLength = findLen;
                maxStart = i - (findLen - 1) / 2;
                maxEnd = i + findLen / 2;
                System.out.println("maxStart: " + maxStart + " maxEnd: " + maxEnd + " maxLength: " + maxLength);
            }
        }
        System.out.println("maxStart: " + maxStart + " maxEnd: " + maxEnd);
        return s.substring(maxStart, maxEnd + 1);
    }

    // 中心擴(kuò)展算法：返回最大的回文字符串長(zhǎng)度
    public int expandAroundCenter(String s, int left, int right) {
        int len = s.length();
        while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
            left --;
            right ++;
        }
        if (left < 0 || right >= len || s.charAt(left) != s.charAt(right)) {
            left ++;
            right --;
        }
        return right - left + 1;
    }

??如果你有疑問(wèn)或更好的算法思路，歡迎留言交流?。。?/strong>
??如果感覺(jué)我的文章對(duì)您有所幫助，麻煩動(dòng)動(dòng)小手給個(gè)喜歡，謝謝?。?！