給定一個字符串 s舀透，找到 s 中最長的回文子串谬返。你可以假設 s 的最大長度為1000旭等。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba"也是一個有效答案俄删。

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

解法一：暴力解法
時間復雜度
兩個for循環(huán)，一個判斷是否為回文的函數(shù)

解法二：中心擴展解法

時間復雜度鹃唯，空間復雜度
c++ code:

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<assert.h>
using namespace std;

class Solution {
public:
    string expand(string s,int left, int right)
    {
        int len = s.size();
        while (  left>=0&& right < len &&s[left] == s[right])//must s[left] == s[right] allocate last,unless crossing
        {
            left--;
            right++;

        }
        return s.substr(left + 1, right - left - 1);
    }
    string longestPalindrome(string s) {
        int len = s.size();
        if (len < 1) return "";
        if (len == 1) return s;

        string maxstr=s.substr(0,1);
        for (int i = 0; i < len; i++)
        {
            string s1 = expand(s, i, i);
            if (s1.size()>maxstr.size())//odd number
            {
                maxstr = s1;
            }
            string s2 = expand(s, i, i + 1);//even number
            if (s2.size()>maxstr.size())
            {
                maxstr = s2;
            }
        }
        return maxstr;
    }
     
};

string stringToString(string input) {
    assert(input.length() >= 2);
    string result;
    for (int i = 1; i < input.length() - 1; i++) {
        char currentChar = input[i];
        if (input[i] == '\\') {
            char nextChar = input[i + 1];
            switch (nextChar) {
            case '\"': result.push_back('\"'); break;
            case '/': result.push_back('/'); break;
            case '\\': result.push_back('\\'); break;
            case 'b': result.push_back('\b'); break;
            case 'f': result.push_back('\f'); break;
            case 'r': result.push_back('\r'); break;
            case 'n': result.push_back('\n'); break;
            case 't': result.push_back('\t'); break;
            default: break;
            }
            i++;
        }
        else {
            result.push_back(currentChar);
        }
    }
    return result;
}

int main() {
    string line;
    while (getline(cin, line)) {
        string s = stringToString(line);

        string ret = Solution().longestPalindrome(s);

        string out = (ret);
        cout << out << endl;
    }
    return 0;
}

中心擴展test

substr
　　　Returns a substring (pos, pos+count).pos開始的位置，count共有多少個瓣喊。

解法三：動態(tài)規(guī)劃
時間復雜度坡慌，空間復雜度

核心思路就是從左開始遍歷，然后不斷的從原字符串中拿出1到length-1長度的字串藻三，進行判斷洪橘。 回文字符串的子串也是回文，比如dp[j,k]（表示以i開始以j結(jié)束的子串）是回文字符串棵帽，那么dp[j+1,k-1]也是回文字符串熄求。這樣最長回文子串就能分解成一系列子問題了。
　　動態(tài)規(guī)劃需要開一個二維數(shù)組逗概，DP[j][k]= s[j]==s[k]&&DP[j+1][k-1]弟晚，時間復雜度較高

初始化：

轉(zhuǎn)移函數(shù)

class Solution {
public:

    string longestPalindrome(string s) {
        int len = s.size();
        if (len < 1) return "";

        vector<vector<int>>Flaglen(len, vector<int>(len, 0));
        int maxlen = 0, index = 0;
        for (int i = 0; i < len; i++)
        for (int j = 0, k = i; j < len&&k < len; j++, k++)
        {
            if (j == k)Flaglen[j][k] = 1;//odd
            else if (j + 1 == k&&s[j] == s[k])
            {
                Flaglen[j][k] = 2;//even
            }
            else if (s[j] == s[k] && Flaglen[j + 1][k - 1])
            {
                Flaglen[j][k] = Flaglen[j + 1][k - 1] + 2;
            }
            else
            {
                Flaglen[j][k] = 0;
            }
            if (Flaglen[j][k]>maxlen)
            {
                index = j;
                maxlen = k - j + 1;
            }
        }
        return s.substr(index, maxlen);
    }


};

動態(tài)規(guī)劃test

解法四：1975年，Manacher算法(馬拉車)
時間復雜度
1.解決長度奇偶性帶來的對稱軸位置問題
　　　插入#解決

string init(string s)
{
    string s1="$#";
    int len=s.size();
    int i;
    for(i=0;i<len;i++)
    {
        s1+=s[i];
        s1+="#";
    }

    return s1;
}

2.解決重復訪問的問題
　　　利用最長id中心的當前i點的對稱點j

if (i < mx)  
    p[i] = min(p[2 * id - i], mx - i);

step 1: 令p[i]=min(p[2*pos-i], mx-i)
step 2: 以i為中心擴展回文串逾苫，直到左右兩邊字符不同卿城，或者到達邊界。
step 3: 更新mx和id

示例：#a#和#a#a#回文半徑分別是2和3铅搓，所以無論奇偶都是 瑟押，p[i] - 1正好是原字符串中最長回文串的長度。
解釋：原始字符串的最大子串狸吞，起始位置的索引centermax - maxlen) / 2勉耀，用下面的圖驗證指煎。除以2是因為加入相同數(shù)的#。

舉例驗證

驗證1：i=5,abba. centermax=5,maxlen=4,pos=0
驗證2：i=16,pxp, centermax=16,maxlen=3,pos=6

class Solution {
public:
    string init(string s)
    {
        string s1 = "$#";//$防越界
        int len = s.size();
        for (int i = 0; i < len; i++)
        {
            s1 += s[i];
            s1 += '#';
        }
        return s1;
    }
    string longestPalindrome(string s) {
        int len1 = s.size();
        if (len1 < 1) return "";

        
        string s_new=init(s);
        int len = s_new.size();
        vector<int>p(len, 0);
        int id = 0, mx = 0;
        for (int i = 1; i < len; i++)//i從1開始忽略$
        {
            if (i < mx)
            {
                p[i] = min(p[2 * id-i], mx - i);
            }
            else//i在mx右邊 必須一個個匹配
            {
                p[i] = 1;
            }
            while (s_new[i - p[i]] == s_new[p[i] + i])
                p[i]++;
            /*我們每走一步 i便斥，都要和 mx 比較至壤，我們希望 mx 盡可能的遠，
            這樣才能更有機會執(zhí)行 if (i < mx)這句代碼枢纠，從而提高效率*/
            if (mx < i + p[i])
            {
                mx = i + p[i];
                id = i;
            }
        }
        /*找最大元素在P中*/
        int centermax = 0, maxlen = 0;
        for (int i = 1; i < len; i++)
        {
            if (p[i] - 1>maxlen)
            {
                maxlen = p[i] - 1;
                centermax = i;
            }
        }
        return s.substr((centermax - maxlen) / 2, maxlen);
    }


};

精益求精99.78%

參考1 此鏈接中心擴展ok像街，動態(tài)規(guī)劃有問題。

參考2
參考3
參考4
Manacher