Problem: *********

思路

动态规划，使用二维数组存放字符串的每一个子串是否为回文子串

解题方法

解题时主要的思路为：

复杂度

• 时间复杂度:

$O(n^2)O(n^2)$

• 空间复杂度:

$O(n^2)O(n^2)$

Code

public:
    string longestPalindrome(string s) {
        int n=s.size();
        if(n<2) return s;
        vector<vector<int>> dp(n,vector<int>(n));//使用
        int maxLen=1;
        int head=0;
        for(int i=0;i<n;++i)
        {
            dp[i][i]=1;//当为一个字符时，为回文字符串
        }
        for(int l=2;l<=n;++l)//长度遍历
        {
            for(int i=0;i<n;++i)//初始点遍历
            {
                int j=i+l-1;//选取的字符串尾部
                if(j>=n)
                {
                    break;
                }
                if(s[i]!=s[j])
                {
                    dp[i][j]=false;
                }
                else
                {
                    if(j-i<3)//小于3，直接为回文字符串
                    {
                        dp[i][j]=true;
                    }
                    else
                    {
                        dp[i][j]=dp[i+1][j-1];
                    }
                }

                if(dp[i][j]&&j-i+1>maxLen)//更新字符串
                {
                    maxLen=j-i+1;
                    head=i;
                }

            }
        }
        return s.substr(head,maxLen);
    }
};

解法优化：中心拓展

复杂度

• 时间复杂度:

$O(n^2)O(n^2)$ ​

• 空间复杂度:

$O(1)O(1)$ ​

Code

class Solution {
public:
    string longestPalindrome(string s) {
        int start=0,end=0;
        for(int i=0;i<s.size();++i)//循环选取字符串中心
        {
            auto [left1,right1]=longestSubStr(s,i,i);
            auto [left2,right2]=longestSubStr(s,i,i+1);

            if(right1-left1>end-start)//中心为一个字符
            {
                start=left1;
                end=right1;
            }
            if(right2-left2>end-start)//中心为两个字符
            {
                start=left2;
                end=right2;
            }
        }
        return s.substr(start,end-start+1);
    }

    pair<int,int> longestSubStr(string s,int left,int right)
    {
        while(left>=0&&right<s.size()&&s[left]==s[right])//从中心拓展开
        {
            --left;
            ++right;
        }
        return {left+1,right-1};//返回
    }
};

进一步优化：不使用调用函数，节约值传递时间花销，当中心为一个字符时，从下一个字符开始判断

public:
    string longestPalindrome(string s) {
        string ans;
        for(int i = 0; i < s.size(); i++)
        {
            int l = i - 1;//一个字符为中心，从下一个位置开始判断
            int r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r])
            {
                --l;
                ++r;
            }
            if(ans.size() < r - l -1)
            {
               ans = s.substr(l+1, r-l-1); 
            }

            l = i, r = i+1;
            while(l >= 0 && r < s.size() && s[l] == s[r])
            {
                --l;
                ++r;
            }
            if(ans.size() < r - l -1)
            {
               ans = s.substr(l+1, r-l-1); 
            }
        }
        return ans;
    }
};