欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【 LeetCode 5】 最长回文子串 (中等) 动态规划

程序员文章站 2022-07-13 23:25:18
...

题目:

【 LeetCode 5】 最长回文子串 (中等) 动态规划


这题和求最长回文子串长度差不多,只需要记录下最长回文字串的首尾索引即可

求最长回文子串思路来自 算法笔记P437

代码:

class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(!len) return ""; //空字符串
        int dp[1000][1000]={0},l=0,r=0; //l r记录首尾索引
        for(int i=0;i<len;i++) //先处理长度为1 和 2的回文
        {
            dp[i][i]=1; //自身为长度1的回文
            if(i<len-1)
            {
                if(s[i]==s[i+1]) //相邻相等,长度为2
                {
                    dp[i][i+1]=1;
                    l=i,r=i+1;
                }        
            }
        }
        for(int i=3;i<=len;i++) //处理长度大于3的回文
        {
            for(int j=0;j+i-1<len;j++) //首索引
            {
                int k=j+i-1; //尾索引
                if(s[j]==s[k] && dp[j+1][k-1]==1)
                {
                    if(r-l+1 <i) l=j,r=k;
                    dp[j][k]=1;
                }
            }
        }
        string ans; //存答案
        for(int i=l;i<=r;i++)
            ans+=s[i];
        return ans;
    }
};

【 LeetCode 5】 最长回文子串 (中等) 动态规划

相关标签: LeetCode