題目

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

示例

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

解題思路

1.暴力法

#python
def get_longest_Palindromic(s):
    window = 0
    max_len = ""
    while(window <= len(s)):
        for i in range(int(len(s))):
            if i+window >int(len(s)):
                window +=1
                break
            if ispalindromic(s[i:i+window]):
                max_len = s[i:i+window]
                window +=1
                break
    return max_len              
def ispalindromic(s):
    if len(s)%2 == 0:
        mid_index = int(len(s)/2)
    else:
        mid_index = int(len(s)/2+1)
    for i in range(mid_index):
        if s[i] != s[-(i+1)]:
            return False
    return True

由于要判斷是否為回文痴鳄，所以時(shí)間復(fù)雜度為，空間復(fù)雜度為县貌，并不能AC.

2.動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃相關(guān)知識(shí)可以點(diǎn)擊鏈接术陶。

#python
class Solution(object):
    def longestPalindrome(self, s):
        dp = [[0]*len(s) for i in range(len(s))]
        max_len = 0
        max_str = ""
        for l in range(len(s)):
            l = l+1
            for start in range(len(s)):
                end = start+l-1
                if end >= len(s):
                    break
                dp[start][end] = (l==1) or (l==2 and (s[start]==s[end])) or (dp[start+1][end-1] and (s[start]==s[end]))
                if dp[start][end] and max_len<l:
                    max_str = s[start:end+1]
        return max_str

動(dòng)態(tài)規(guī)劃也可以看作是一種更聰明的暴力法，因?yàn)榭梢詼p少重復(fù)計(jì)算煤痕。時(shí)間復(fù)雜度和空間復(fù)雜度都是

3.中心擴(kuò)展

我們觀察到回文中心的兩側(cè)互為鏡像梧宫。因此，回文可以從它的中心展開(kāi)摆碉，并且只有 2n?1 個(gè)這樣的中心塘匣。你可能會(huì)問(wèn)，為什么會(huì)是 2n?1 個(gè)巷帝，而不是 n 個(gè)中心忌卤？原因在于所含字母數(shù)為偶數(shù)的回文的中心可以處于兩字母之間（例如 “abba” 的中心在兩個(gè) ‘b’ 之間）。

#python
def get_longest_Palindromic_1(s):
    max_len = 0
    s_t = ""
    for i in range(len(s)):
        len1 = expandAroundCenter(s,i,i)#奇數(shù)回文串
        len2 = expandAroundCenter(s,i,i+1)#偶數(shù)回文串
        len_3 = max(len1,len2)
        if max_len< len_3:
            max_len = len_3
            s_t = s[i-int((max_len-1)/2):i+int(max_len/2)+1]
    return s_t
def expandAroundCenter(s,left,right):
    while(left>=0 and right < len(s) and s[left] == s[right]):
        left = left-1
        right = right +1
    return right-left-1

中心擴(kuò)展時(shí)間復(fù)雜度楞泼，空間復(fù)雜度

Mnacher(馬拉車(chē))

算法詳情點(diǎn)擊鏈接.

#java
public String preProcess(String s) {
    int n = s.length();
    if (n == 0) {
        return "^$";
    }
    String ret = "^";
    for (int i = 0; i < n; i++)
        ret += "#" + s.charAt(i);
    ret += "#$";
    return ret;
}

// 馬拉車(chē)算法
public String longestPalindrome2(String s) {
    String T = preProcess(s);
    int n = T.length();
    int[] P = new int[n];
    int C = 0, R = 0;
    for (int i = 1; i < n - 1; i++) {
        int i_mirror = 2 * C - i;
        if (R > i) {
            P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
        } else {
            P[i] = 0;// 等于 R 的情況
        }

        // 碰到之前講的三種情況時(shí)候驰徊，需要利用中心擴(kuò)展法
        while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
            P[i]++;
        }

        // 判斷是否需要更新 R
        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }

    }

    // 找出 P 的最大值
    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2; //最開(kāi)始講的求原字符串下標(biāo)
    return s.substring(start, start + maxLen);
}