最长回文子串

letcode 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串
如果字符串的反序与原始字符串相同，则该字符串称为回文字串。

示例1

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

解题思路

此题可以用动态规划的思想去解决

1.明确dp[i][j]的含义

dp数组在此题中代表下标从i到j的回文字符串，
若为回文字符字串，则dp[i][j]为1，其余为0

2.写出动态转移方程

1. 判断s[i]与s[j]是否相等
2. 如果相等，则有三种情况： i==j；j-i=1；j-i>1前两种情况可以写成 j-i<=1，此时dp[i][j]=1
3. 第三种情况：若要此时数组为回文字符字串，则它们中间的为回文字符串，i，i+1，i+2，…，j-1，j，即dp[i+1][j-1]
4. 此时的状态转移方程为 dp[i][j]=dp[i+1][j-1]

判断循环的方向

 由于dp[i][j]=dp[i+1][j-1],即dp[i+1][j-1]在dp[i][j]在dp[i+1][j-1]的右上角，所以要从下到上，并且j的值从i到s的长度

最后

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.size();
        if(n==0||n==1)
        {
            return s;
        }
        //定义一个二维数组用来表示从i到j的字符串是否为回文字符串
        vector<vector<int >> dp(n,vector<int>(n));
        //left表示最长回文字符串的左边，right代表右边
        int left=0;
        int right=0;
        for(int  i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                {
                    if(j-i<=1)
                    {
                        dp[i][j]=1;
                    }
                    else
                    {
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                if(dp[i][j]&&right-left<j-i)//用来更新最长的回文字符串
                {
                    left=i;
                    right=j;
                }
            }
        }
        return s.substr(left,right-left+1);
    }
};