//暴力求解
/*判断字符串所有的长度大于1的字串是否为回文串 若字符串长度过长 耗时较长
时间复杂度O（n^3) 找出所有的字符串0（n^2),每一个判断耗时O(n)
//判断是否为回文串的函数
bool isPalindrome(string s){
string str;
str = s;
reverse(s.begin(),s.end());
if(s==str)
return true;
else
return false;
}
//返回最长的子串下标
int longestIndex(vector<string> s)
{ int index =0;
int max =s[0].length();
for(int i =1;i<s.size();++i)
if(max<s[i].length())
{
max=s[i].length();
index =i;
}
return index;
}
string longestPalindrome(string s) {
vector<string> str1;
if(s=="")str1.push_back("");
string s1 ="";
for(int i = 0;i<=s.length();++i)
{
for(int j = 1;j<=s.length()-i;++j)
{
s1=s.substr(i,j);//获取s的子串
if(isPalindrome(s1))//判断子串是否为回文串
{
str1.push_back(s1);// 存进vector str1;
}
}
}
return str1[longestIndex(str1)];
}
//动态规划
我们定义P{i，j}为字符串从i到j的子字符串；
P{i，j} =true 表示该字串为回文串，false 则不是
初始化p{i，i} =true；
当S[i] =s[i+1] 则P{i，i+1}=true；
若P{i，j}为true 且S[i+1]==S[j-1] p{i+1，j-1}也为true
如此空间复杂度度为O（n^2) 时间复杂度也为O（n^2)
string longestPalindrome(string s) {
if(s == "" || s.length() == 1){
return s;
}
bool p[1005][1005] ;
int start = 0;//跟踪最长回文串的初始位置
int maxlen =1；//返回值最长回文串的长度
int len =s.length();
for(int i =0;i<len;i++)
{
p[i][i] =true;
if(i<len-1 &&s[i]==s[i+1]){
p[i][i+1] =true;
start = i;
maxlen = 2;
}
}
for(int m =3;m<=len;m++){
for(int i = 0;i<=len-m;i++){
int j = i+m-1;
if(p[i+1][j-1] && s[i] == s[j])
{ p[i][j] = true;
start =i;
maxlen =m;
}
}}return s.substr(start,maxlen);}