LeetCode刷题（2）最长回文子串

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:

Input: “cbbd”
Output: “bb”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

My Solution

class Solution {
public:
    string longestPalindrome(string s) {
        string temp="",maxStr="";
        int maxLeft=0,maxRight=0,max=0;
        if(s.size()<=1)
            return s;
        for(int i=0;i<s.length();i++)
        {
            for(maxRight=maxStr.length()+i;maxRight<=s.length();maxRight++)
            {
                temp=s.substr(i,maxRight-i);
                
                int val=checkPaling(temp);
                
                if(val>max)
                {
                    max=temp.length();
                    maxStr=temp;
                }
            }
        }
        return maxStr;

        
    }
    int checkPaling(string s)
    {
        int len=0;
        if(s.empty())
            return 0;
        if(s.size()%2)
        {
            for(int i=0;i<s.length();i++)
            {
                if(s[i]==s[s.length()-1-i])
                    len++;
                else
                    return 0;
            }
        }else
        {
            for(int i=0;i<=s.length();i++)
            {
                if(s[i]==s[s.length()-1-i])
                    len++;
                else
                    return 0;
            }

        }
        return len;
    }
};

插曲：当测试字符串过长的时候会出现
Line 506: Char 9: runtime error: pointer index expression with base 0x000000000000 overflowed to 0xffffffffffffffff (basic_string.h)
逻辑是没有错误的，但是内存开销在小内存机器上很容易出错，错误出现的主要原因是在string 不断赋值分配再释放空间产生大量的内存碎片导致堆区溢出，。
其实上面的错误出现的原因是我输入的时候没有加上””，加上后就好了。
提交的时候出现错误是在
"babaddtattarrattatddetartrateedredividerb"

后面发现当回文字符个数为偶数的时候就会出现这个错误，自己输入很长乱七八糟的都没问题，排除内存问题。结果是自己出现了个很小很小的错误

   for(int i=0;i<s.length();i++)   //这里i<s.length()
            {
                if(s[i]==s[s.length()-1-i])
                    len++;
                else
                    return 0;
            }
```  
#### 最后提交也没通过，因为时间复杂度太高了。。。

## 下面是动态规划方面的题解

初始状态：

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

class Solution {
public:
string longestPalindrome(string s) {
int len=s.size();
if(len==0||len==1)
return s;
int start=0;//回文串起始位置
int max=1;//回文串最大长度
vector<vector> dp(len,vector(len));//定义二维动态数组
for(int i=0;i<len;i++)//初始化状态
{
dp[i][i]=1;
if(i<len-1&&s[i]==s[i+1])
{
dp[i][i+1]=1;
max=2;
start=i;
}
}
for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
{
for(int i=0;i+l-1<len;i++)
{
int j=l+i-1;//终止字符位置
if(s[i]==s[j]&&dp[i+1][j-1]==1)//状态转移
{
dp[i][j]=1;
start=i;
max=l;
}
}
}
return s.substr(start,max);//获取最长回文子串
}
};