5. 最長(zhǎng)回文子串

題目描述

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

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

示例 2：
輸入: "cbbd"
輸出: "bb"

算法思想

解法一：暴力算法
暴力算法應(yīng)該是本題的最基礎(chǔ)解法了，基本思路是這樣的：判斷以索引位置i (0 <= i < len)為起始位置，長(zhǎng)度分別為 j (2 <= j <= len - i) 的子串是否為回文串，同時(shí)使用變量startIndex來(lái)記錄最長(zhǎng)回文子串的起始位置，maxLength來(lái)記錄最長(zhǎng)回文子串的長(zhǎng)度。

解法二：動(dòng)態(tài)規(guī)劃
遇到最值問(wèn)題，我們一般都會(huì)往貪心或者動(dòng)態(tài)規(guī)劃上靠攏。顯然，這一題可以采用動(dòng)態(tài)規(guī)劃來(lái)實(shí)現(xiàn)，但是，對(duì)于動(dòng)態(tài)規(guī)劃的問(wèn)題，我們腦海中能很快的浮現(xiàn)出解題 “三部曲”：
1）定義狀態(tài)
2）根據(jù)定義的狀態(tài)寫(xiě)出狀態(tài)轉(zhuǎn)移方程
3）考慮邊界

而在這“三部曲”中最難的就是第一步，即如何定義狀態(tài)？，如果根據(jù)定義的狀態(tài)很難寫(xiě)出狀態(tài)轉(zhuǎn)移方程，那么就要考慮狀態(tài)定義的是否正確。

針對(duì)本題而言：
1）定義狀態(tài)：dp[i][j]用來(lái)表示子串s[i, j]是否為回文串，這里的子串s[i, j]為閉區(qū)間，且有i < j
2）狀態(tài)轉(zhuǎn)移方程：如果子串s[i, j]是回文串，那么子串s[i+1, j-1]必然也是回文子串，因此，狀態(tài)轉(zhuǎn)移方程
dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
3）考慮邊界：此題的邊界為s[i+1, j-1]不會(huì)構(gòu)成一個(gè)閉區(qū)間，即s[i+1, j-1]的長(zhǎng)度小于2，即(j-1) - (i+1) +1 < 2，得到j - i < 3 。
在j - i < 3 的前提下，如果s[i] == s[j] 且 s[i+1, j-1]為空串或者只包含1個(gè)字符，則直接判斷s[i ... j]為回文串。

代碼實(shí)現(xiàn)

解法一：暴力算法

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 2) {
            return s;
        }
        int startIndex = 0;
        int maxLength = 1;
        for (int i = 0; i < len; i++) {
            // 如果以i起始位置一直到原字符串結(jié)尾的子串，其長(zhǎng)度小于maxLength，說(shuō)明該子串肯定不會(huì)包含最長(zhǎng)回文子串
            for (int j = 2; j <= len - i && maxLength < len -i; j++) {
                String substr = s.substring(i, i + j);
                // 如果以i起始位置，長(zhǎng)度為j的子串是回文串，且長(zhǎng)度大于maxLength，則更新起始位置startIndex和maxLength
                if (isPalindrome(substr) && substr.length() > maxLength) {
                    startIndex = i;
                    maxLength = j;
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLength);
    }

    /**
    * 判斷一個(gè)字符串是否為回文串
    **/
    public static boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}

算法的時(shí)間復(fù)雜度為O(n^3)，空間復(fù)雜度為O(1)

解法二：動(dòng)態(tài)規(guī)劃

class Solution {
    public static String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        // dp[i][j]用來(lái)存儲(chǔ)子串s[i...j]是否為回文串
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len ; i++) {
            Arrays.fill(dp[i], true);
        }
        int startIndex = 0;
        int maxLength = 1;

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    startIndex = i;
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLength);
    }
}

時(shí)間復(fù)雜度為O(n^2)
空間復(fù)雜度為O(n^2)，即dp問(wèn)題一般都是采用空間來(lái)?yè)Q時(shí)間。