Leetcode-5.最长回文子串

发表于 2019-08-21 分类于 1-100 阅读次数：

题目描述

lc5

解法1：动态规划

1.定义dp数组

定义一个bool型dp二维数组dp[i][j]，i表示开始位置，j表示结束位置,true表示是回文子串

2.初始状态

dp[i][i]=1; //单个字符是回文串
dp[i][i+1]=1 if s[i]=s[i+1]; //连续两个相同字符是回文串

3.状态转移方程

dp[i][j]=dp[i+1][j-1]&& $s_i==s_j$

4.初始化一字母和二字母回文，然后找到所有三字母，以此类推

class Solution {
public:
    string longestPalindrome(string s) {
        
        int n=s.length();
        if(n<=1)
            return s;
        vector<vector<int>>  bp(n,vector<int>(n));//定义二维动态数组
        int l;
        int length=1;
        int start=0;
        int i;
        for(i=0;i<n;i++)
        {
            bp[i][i]=1;
            if((i<n-1)&&s[i]==s[i+1])
            {
                bp[i][i+1]=1;
                length=2;
                start=i;
            }
        }
        for(l=3;l<=n;l++)
        {
            for(i=0;i+l-1<n;i++)
            {
                int j=i+l-1;
                if(s[i]==s[j]&&(bp[i+1][j-1]==1))
                {
                    bp[i][j]=1;
                    length=l;
                    start=i;
                }
            }
        }
        return s.substr(start,length);
    }
};

复杂度分析

时间复杂度（$n^2$）
空间复杂度（$n^2$）

解法2：中心扩展算法

事实上，只需使用恒定的空间，我们就可以在 O($n^2$) 的时间内解决这个问题。

我们知道回文串一定是对称的，所以我们可以每次循环选择一个中心，进行左右扩展，判断左右字符是否相等即可。

由于存在奇数的字符串和偶数的字符串，所以我们需要从一个字符开始扩展，或者从两个字符之间开始扩展，所以总共有 n + n - 1 个中心。

class Solution {
public:
    string longestPalindrome(string s) {
        
        int n=s.length();
        if(n<=1)
            return s;
        int start=0;
        int i;
        int length=1;
        for(i=0;i<s.length();i++)
        {
            int len1=expandAroundCenter(s,i,i);
            int len2=expandAroundCenter(s,i,i+1);
            int len=max(len1,len2);
            if(len>length)
            {
                start=i-(len-1)/2;
                length=len;
            }
        }
        return s.substr(start,length);
    }
    int expandAroundCenter(string s,int left,int right)
    {
        int l=left,r=right;
        while(l>=0&&r<s.length()&&s[l]==s[r])
        {
            l--;
            r++;
        }
        return r-l-1;
    }
};