动态规划：
1个回文串，两边加上同样的字符，也是回文串。这是一个性质，之后要用。
对于一大串字符，从1长度的子串开始判断。
1个长度的子串，肯定回文；如果这个子串两边加上同样的字符，长度变成了3，少了一次判断。
因此还要加上，判断2长度的子串是不是回文。
之后才会判断3长度的子串是不是回文。
以此类推。
看图说明，假设有这么一个字符串“abbab"
列一个二维数据表，这个表存储了所有子串的情况。如下。| a | ab | abb | abba | abbab |
| b | bb | bba | bbab | |
| b | ba | bab | ||
| a | ab | |||
| b |
| 1 | 0 | |||
| 1 | 1 | |||
| 1 | 0 | |||
| 1 | 0 | |||
| 1 |
那么3长度的子串是不是回文，用一下回文的性质。 3长度，看它首尾是否相等，中间字串是否回文。 4长度，看它首尾是否相等，中间字串是否回文。 首尾字符是否相等这个判断很简单，而它中间的字串是否回文，取决于我们之前算的这个表。 比如0，3位置的子串“abb”是否回文，取决于"a"和“b"以及中间子串b ，而"b"之前已经算过了；只需要额外判断一下"a","b"即可。 转换成动态转移方程 str(begin,end)=str(begin+1)(end-1)&&s[begin]==s[end]; 因此这个表出来了
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | |
| 1 | 0 | 1 | ||
| 1 | 0 | |||
| 1 |
代码如下：
class Solution {
public:
string longestPalindrome(string s) {
if (s.size()<2) return s;
vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
string ans=s.substr(0,1);
for(int i=0;i<s.size();i++)
{
dp[i][i]=1;
}
for(int i=0;i<s.size()-1;i++)
{
if(s[i]==s[i+1])
{
dp[i][i+1]=1;
ans=s.substr(i,2);
}
}
for(int length=2;length<=s.size();length++)
{
for(int i=0;i<s.size()-length+1;i++)
{
if(dp[i+1][i+length-2]==1&&s[i]==s[i+length-1])
{
dp[i][i+length-1]=1;
ans=s.substr(i,length);
}
}
}
return ans;
}
};
问题是空间复杂度和时间复杂度都是O（N2）
更优的解法之后更新。
标签：子串,leetcode5,string,是否,判断,长度,回文 From： https://www.cnblogs.com/HaveFunnyAnyone/p/17500283.html