5.最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”
输出: “bb”

C++

• 动态规划，dp[i][j]表示从i到j的是否是回文串
• dp[i][j]的状态可以通过dp[i+1][j-1]是否为回文串，以及s[i]是否与s[j]相等来推断
• 需要先构造回文串长度为1和2时的情况

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.length();
        if(len<1) return s;
        int st=0,maxlen=1;
        int dp[1000][1000]={0};
        for(int i=0;i<len;i++){
            dp[i][i]=1;
            if(i<len-1){
                if(s[i]==s[i+1]){
                    dp[i][i+1]=1;
                    maxlen=2;
                    st=i;
                }
            }
        }
        for(int l=3;l<=len;l++){
            for(int i=0;i+l-1<len;i++){
                int j=i+l-1;
                if(s[i]==s[j] && dp[i+1][j-1]==1){
                    dp[i][j]=1;
                    maxlen=l;
                    st=i;
                }
            }
        }
        return s.substr(st,maxlen);
    }
};

Python

class Solution(object):
    def longestPalindrome(self, s):
        n = len(s)
        if n < 2 or s == s[::-1]:
            return s
        max_len = 1
        start = 0
        for i in range(1,n):
            even = s[i-max_len:i+1]
            odd = s[i-max_len-1:i+1]
            if i-max_len-1>=0 and odd == odd[::-1]:
                start = i-max_len-1
                max_len += 2
                continue
            if i-max_len>=0 and even == even[::-1]:
                start = i-max_len
                max_len += 1
        return s[start:start+max_len]