题解 | #最长回文子串#
最长回文子串
http://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
力扣第五题,动态规划一下,注意循环的方向,转化为的子问题应该是遍历过的,求最大长度应该判断是否大于当前最大。如果不是就不更新
#include <algorithm>
#include <vector>
using namespace std;
int main() {
string str;
while(cin>>str){
int n = str.size();
int maxlen = -1;
vector<vector<bool>> v(n,vector<bool>(n,false));
for(int i = 0 ;i<n;i++){//这里赋值边界条件其实还应该判断输入是否是1个字符或者两个,这里没判断,样例没有给这种例子,可以AC
v[i][i] = true;
}
for(int i = 0 ;i<n-1;i++){
if(str[i]==str[i+1]){
v[i][i+1]=true;
maxlen=2;
}
}
for(int i = 2;i<n;i++){
for(int j =0;j<i-1;j++){
if(str[i]==str[j]){
v[j][i]=v[j+1][i-1];
}
if(v[j][i]&&(i-j+1)>maxlen) maxlen=i-j+1;//这判断最大长度超过没
}
}
cout<<maxlen<<endl;
}
}