LeetCode/最长回文子串
描述
对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
思路
1.暴力列举所有串，判断串是否为回文串并将当下最长的进行存储
2.中心扩散，顺序遍历，对每个点进行左右同时扩散，得到其中心点对应的最大回文串和回文串长度（考虑奇偶串要分别用一个中心和两个中心点进行遍历），时间复杂度为O(n2)，空间复杂度为O(1)
3.动态规划，用二维dp数组记录任意两点间是否为回文串
状态转移方程：dp[i][j]=(s[i]==s[j])and dp[i+1][j-1]
边界条件：j-i<3(即字符串长度为2和3时不用再检查子串)
合理的递推顺序(小串到大串)即能把任意两点是否为回文串计算出来
时间复杂度为O(n2)，空间复杂度为O(n2)
4.Manacher算法，中心扩散的时候可以结合动态规划的思想，将已经扩散计算过的点进行存储，使得算法性能成为线性
中心扩散C++
点击查看代码
class Solution {
public:
string longestPalindrome(string s) {
int maxlen = 1;//单字符进不了循环默认为1
int begin,single,doubles;
begin = 0;
for(int i=0;imaxlen&&single>doubles){
maxlen = single;
begin = i-maxlen/2;
}
else if(doubles>maxlen){
maxlen = doubles;
begin = i-maxlen/2+1;
}
}
return string(s,begin,maxlen);
}
//fun函数返回指定中心点的回文串长度
int fun(string &s,int begin,int end){
while(begin>=0 && end 动态规划C++
点击查看代码
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
vector> dp(n, vector(n));
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= n; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < n; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= n) {
break;
}
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxLen);
}
};