法1:动态规划
时间复杂度和空间复杂度都是O(n^2)
class Solution {
public:
//上三角矩阵存入一维数组的坐标映射
int pos_reflex(int i, int j)
{
return i + j * (j + 1) / 2;
}
void set_value(bool v, int i, int j)
{
// i<=j, always
// start with 0
statu_matrix[pos_reflex(i, j)] = v;
}
bool get_value(int i, int j)
{
return statu_matrix[pos_reflex(i, j)];
}
string longestPalindrome(string s) {
int n = s.size();
// 记录是否回文的三角矩阵
statu_matrix = new bool[n * (n + 1) / 2];
//预置长度为1的子串：一定是回文串
//预置长度为2的子串：没有存i + 1, j - 1的值
set_value(true, 0, 0);
for (int j = 1; j < n; j++)
{
set_value(true, j, j);
set_value(s[j - 1] == s[j], j - 1, j);
for (int i = 0; i < j - 1; i++)
set_value(get_value(i + 1, j - 1) && s[i] == s[j], i, j);
}
//只能输出一个，多个需要容器
int pi = 0;
int max = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
if (get_value(i, j) && j - i + 1 > max)
{
pi = i;
max = j - i + 1;
}
return s.substr(pi, max);
}
private:
bool *statu_matrix ;
};
动态规划算法的效果
法2:中心扩展算法
分别从长度为1和长度为2的子串同时向两侧扩展。有2n-1个中心，只有奇数和偶数中心两种情况，而奇数中心一定由1中心扩展来，偶数同理。
每个中心都至多要展开n/2，因此时间复杂度仍是O(n^2)。
这个方法把空间复杂度降到了O(1)
class Solution {
public:
int check(int l, int r, int n, int max, string &str)
{
//同时向两侧扩展
while (l >= 0 && r < n)
{
if (str[l] == str[r])
max += 2;
else
break;
l -= 1;
r += 1;
}
return max;
}
void update_records(int c, int &max, int &start, int len)
{
if (len <= max)
return;
max = len;
start = c - (len - 1) / 2;//回文串的开始
}
string longestPalindrome(string s) {
if (s.size() == 1)
return s;
int max = 1;
int pi = 0;
for (int c = 0; c < s.size(); c++)
{
// 中心长度为1
update_records(c, max, pi, check(c - 1, c + 1, s.size(), 1, s));
// 中心长度为2
update_records(c, max, pi, check(c, c + 1, s.size(), 0, s));
}
return s.substr(pi, max);
}
};
中心扩展算法的效果比动态规划要好上不少。
