题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example1：

Input: "babad"

Output: "bab"

Note: "aba is also a valid answer. "

Example2：

Input: "cbbd"

Output: "bb"

思路

思路1：动态规划

Step1：刻画一个最优解方程

\(dp[i][j]\)表示子串\(s[i, \cdots,j]\)是否是一个回文子串

Step2：递归定义最优解的值

（1）初始化：

dp[i][i] = true, i = [0, 1, ... ,n-1];
dp[i][i-1] = true, i = [1,2,...,n-1]
其余为false

（2）状态转移表

dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])

状态转移表更新如图1：

Step3：计算最优解的值

根据状态转移表，以及递推公式，计算dp[i][j]。

思路2：中心扩展法

以某字符为中心，分别计算回文长度。分为回文子串为奇数、偶数两种情况

奇数：以当前遍历字符为中心判断
偶数：以当前遍历字符与其相邻字符为中心判断

思路3：Manacher算法

又称为马拉车算法，可以在时间复杂都为O(n)的情况下求解一个字符串的最长回文子串的问题。

Manacher算法通过为字符串虚拟增加#（并不是真的增加#），使得长度为奇数和长度为偶数的回文子串放在一起考虑（使得回文子串长度都为奇数），如图1。具体操作：在字符串的首部、尾部、相邻字符之间虚拟增加#号。

（1）Len数组的性质

（2）Len数组的计算

思路4：字符串分片（python）

利用字符串的分片操作来检测是否是回文。

Tips

动态规划

将待求解问题分解为若干个非互相独立的子问题，先求子问题，再求原问题。（通常需要将不同阶段的不同状态保存在二维数组内）。

C++

思路1

class Solution {

public:

    string longestPalindrome(string s) {

        int nLength = s.size();

        if(nLength<1)

            return s;

        vector<vector<bool> > dp(nLength, vector<bool>(nLength, 0)); //dp[i][j]表示子串s[i,...,j]是否是一个回文子串

        int strBegin = 0;  //回文子串的开始

        int strEnd = 0; //回文子串的结尾

        //初始化

        for(int i = 1;i < nLength; i++){

            dp[i][i] = true;

            dp[i][i-1] = true;  //这个是针对子串长度为2，"bb"、"aa"的情况

        }

        dp[0][0] = true;

        //动态规划

        for(int i = 2;i <= nLength; i++){ //回文长度

            for(int j = 0; j <= nLength - i ; j++){  //回文子串起始

                if(s[j] == s[i+j - 1] && dp[j+1][i+j-2]){

                    dp[j][j+i-1] = true;

                    if(strEnd - strBegin + 1 < i){

                        strBegin = j;

                        strEnd = i + j -1;

                    }

                }

            }

        }

        return s.substr(strBegin,strEnd-strBegin+1);

    }

};

思路2

class Solution {

public:

    string longestPalindrome(string s) {

        int nLength = s.size();

        if(nLength == 1)

            return s;

        int strBegin = 0;

        int maxLength = 0;

        for(int i = 1;i < nLength; i++){

            //如果回文子串是奇数，以i为中心搜索

            int left = i - 1;

            int right = i + 1;

            while(left >=0 && right < nLength && s[left] == s[right] )

            {

                left --;

                right ++;

            }

            if(right - left - 1 > maxLength){ //right -1 - (left + 1) + 1

                maxLength = right - left - 1;

                strBegin = left + 1;

            }

            //如果回文子串是偶数,

            left = i - 1;

            right = i;

            while(left >=0 && right < nLength && s[left] == s[right]){

                left --;

                right ++;

            }

            if(right - left - 1 > maxLength){

                maxLength = right - left - 1;

                strBegin = left + 1;

            }

        }

        return s.substr(strBegin,maxLength);

    }

};

思路3

class Solution {

public:

    string longestPalindrome(string s) {

        if(s.size() <= 1)

            return s;

        string dummy = init(s);

        int nLength = dummy.size();

        int maxLen = 0;

        int mx = 0;

        int id = 0;

        vector<int> len(nLength, 0);

        for(int i =1;i< nLength - 1; i++){

            if(i < mx)

                len[i] = min(len[2*id -i], mx - i);

            else

                len[i] = 1;

            while(dummy[i - len[i]] == dummy[i + len[i]])

                len[i] ++;

            if(mx < i + len[i]){

                id = i;

                mx = i + len[i];

            }

        }

        int index = 0;

        for(int i = 1; i < nLength-1; i++){

            if(len[i] > maxLen){

                maxLen = len[i];

                index = i;

            }

        }

        return s.substr((index - maxLen)/2, maxLen-1);

    }

    //初始化

    string init(const string& s){

        string result = "$#";

        int nLength = s.size();

        for(int i=0;i < nLength; i++){

            result.push_back(s[i]);

            result.push_back('#');

        }

        return result;

    }

};

Python

class Solution(object):

    def longestPalindrome(self, s):

        """

        :type s: str

        :rtype: str

        """

        if len(s) == 1:

            return s

        result = ""

        for i in range(len(s)):

            j = i + 1

            while j <= len(s) and len(result) <= len(s[i:]):

                if s[i:j] == s[i:j][::-1] and len(s[i:j]) > len(result):

                    result = s[i:j]

                j += 1

        return result

参考

[1] https://blog.csdn.net/suool/article/details/38383045

巴特西

5. Longest Palindromic Substring[M]最长回文子串

题目

思路