算法:动态规划
时间复杂度:O(n^2)
闫氏dp分析法
状态表示:d[i,j]
集合:从i位置到j位置为回文字符串
属性:最大值
状态计算:
d[i,j] = d[i+1,j-1]
如果字符串从i到j是回文字符串,那么去掉首尾两个字符也是回文字符串,即从i+1到j-1也是回文字符串
如果字符串小于等于2,那么该子串一定是回文字符串
最后计算最大长度时,一定要保证从i到j是回文字符串,且i到j长度大于最大长度,才更新最大长度,和初始位置
代码#include
#include
#include
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
int maxlength = 1;//回文字符串最大长度
int begin = 0;//初始位置
if(n < 2) return s;
vector<vector<int>> d(n,vector<int>(n));
//给所有长度为1的子串都设为回文子串
for(int i = 0;i<n;i++)
d[i][i] = true;
//先遍历长度,在遍历左边界,由长度和左边界算出右边界
for(int L = 2;L<=n;L++)
{
for(int i = 0;i<n;i++)
{
int j = i + L - 1;
//如果右边界越界,跳出循环
if(j>=n) break;
if(s[i] != s[j])
{
d[i][j] = false;
}
else
{
if(j - i < 3)
{
d[i][j] = true;
}
else
{
d[i][j] = d[i+1][j-1];
}
}
//如果从i到j是回文数字,且长度大于最大长度,就更新最大长度和开始位置
if(d[i][j] && j-i+1>maxlength)
{
maxlength =j-i+1;
begin = i;
}
}
}
return s.substr(begin,maxlength);
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)