题目描述
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
解题方法
1、动态规划算法
解题思路
（1）考虑回文串的性质：若一个子串是回文串并且长度大于2，则将其首尾两个字母去除后，该子串仍然是一个回文串，反过来思考，若一个子串是回文串，在其首尾分别添加一个字母，若字母相同，则形成的子串也是回文串。
（2）状态表示：回文串有三个重要的性质：起始字母下标、终止字母下标以及长度，其中长度可以由前两个性质推导得出，则使用二维数组dp(i,j)表示，dp(i,j)的值表示的也不再是区间[i,j]的最大回文子串的长度了，而是表示区间 [i,j]是否是回文串。
若 dp(i,j)=true，表示Si....Sj是一个回文串，反之则不是一个回文串。
（3）初始化：每个字符本身就是一个回文串
for (int i = 0; i < n; i++)
{
dp[i][i] = true;
}（4）状态转移：由（1）可得，当j-i>=3时，dp(i,j)的值由两个因素决定：s[i]与s[j]的值，dp(i+1,j-1)，并且仅当以下两个条件同时成立时，dp(i,j)为true
当j-i<3时，存在两种情况：
①j-i=1，则dp(i,j)一定为true（a、b)；
②j-i=2，若此时s[i]==s[j]，则dp(i,j)为true（ab、aa）；
其中第二种情况可以归纳到一般情况的计算中，只需要添加一个条件判断即可。
因为需要使用到dp(i+1,j-1)的值，递推时从长度较小的字符串向长度较长的字符串进行转移（即先计算较小的区间，再计算较大的区间）。
（5）代码流程：当区间大小为1时（即i==j），一定是回文串，因此只需要讨论区间长度在[2,n]之间的情况。外层循环表示每次判断的区间大小L，内层循环固定右边界（即i的大小），j的值可以由L和i推导得到（j=L+i-1)，因此不需要再加一层循环。同时需要注意左边界越界问题（j>=n)，一旦越界就可以退出当前循环，右边界不存在越界问题。
在循环中，一旦s[i]!=s[j]则表示区间[i,j]不可能形成回文串，置dp(i,j)=false；若s[i]==s[j]，当L<=3时不需要判断dp(i+1,j-1)的情况，直接置dp(i,j)=true，当L>3时，需要判断dp(i+1,j-1)，当且仅当dp(i+1,j-1)=true时，置dp(i,j)= true。
代码实现
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<vector<int>> dp(n, vector<int>(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 {
// 处理当j-i==2时的特殊情况
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);
}
};复杂度分析
（1）时间复杂度
外层循环n次，内层循环n次，则时间复杂度为O(n^2)。
（2）空间复杂度
动态规划数组存储空间为nxn，则空间复杂度为O(n^2)。
2、中心扩展算法
解题思路
（1）在动态规划方法中，每一次判断s[i]==s[j]之后，我们都会再判断dp(i+1,j-1)的情况。事实上可以考虑以回文子串为扩展中心，向（i-1,j+1）方向扩展，若s[i-1]==s[j+1]则可以扩展回文子串的长度，一旦不相等则停止继续扩展回文子串。
（2）代码流程：先枚举出所有的回文中心，再尝试向左向右同时进行扩展，最后求出所有扩展回文串的最大值得到最大回文串长度。
注意：因为奇数长度的回文串和偶数长度的回文串结构不太一样，偶数长度的回文串没有中心字符，因此枚举时需要以长度为1的子串作为回文中心（扩展得到奇数长度的回文串）也需要以长度为2的子串作为回文中心（扩展得到偶数长度的回文串）。
（3）标准模板库——pair
作用：
①pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。
pair<string, string> anon;②另一个应用是，当一个函数需要**返回2个数据**的时候，可以选择pair。
pair<int, int> expandAroundCenter(const string& s, int left, int right)
{
// 省略
return {left + 1, right - 1};
}性质：
①pair中的两个数据可以具有不同的数据类型。
pair<int, double> p1(1, 1.2);②两个数据可以分别用pair的两个公有函数first和second访问。
pair<int ,double> p1;
p1.first = 1;
p1.second = 2.5;
cout<<p1.first<<' '<<p1.second<<endl;代码实现
class Solution {
public:
pair<int, int> expandAroundCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
// 返回满足要求的回文串起始索引
return {left + 1, right - 1};
}
string longestPalindrome(string s) {
// 使用变量start和end跟踪最大扩展回文子串
int start = 0, end = 0;
// 枚举所有可能的长度为1或2的回文中心
for (int i = 0; i < s.size(); ++i) {
// 以一个字符作为回文中心进行扩展
auto [left1, right1] = expandAroundCenter(s, i, i);
// 以两个字符作为回文中心进行扩展
auto [left2, right2] = expandAroundCenter(s, i, i + 1);
// 更新记录
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
return s.substr(start, end - start + 1);
}
};
复杂度分析
（1）时间复杂度
回文中心共有n个，每个回文中心最多向外扩展n次，则时间复杂度为O(n^2)。
（2）空间复杂度
使用了变量start、end作为跟踪变量（常数），则空间复杂度为O(n)。
3、Manacher算法
class Solution {
public:
int expand(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left;
++right;
}
return (right - left - 2) / 2;
}
string longestPalindrome(string s) {
int start = 0, end = -1;
string t = "#";
for (char c: s) {
t += c;
t += '#';
}
t += '#';
s = t;
vector<int> arm_len;
int right = -1, j = -1;
for (int i = 0; i < s.size(); ++i) {
int cur_arm_len;
if (right >= i) {
int i_sym = j * 2 - i;
int min_arm_len = min(arm_len[i_sym], right - i);
cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
} else {
cur_arm_len = expand(s, i, i);
}
arm_len.push_back(cur_arm_len);
if (i + cur_arm_len > right) {
j = i;
right = i + cur_arm_len;
}
if (cur_arm_len * 2 + 1 > end - start) {
start = i - cur_arm_len;
end = i + cur_arm_len;
}
}
string ans;
for (int i = start; i <= end; ++i) {
if (s[i] != '#') {
ans += s[i];
}
}
return ans;
}
};（1）时间复杂度：O(n)
（2）空间复杂度：O(n)文章来源：https://www.toymoban.com/news/detail-844785.html
该算法时间复杂度和空间复杂度均较低，但是算法复杂，不在掌握范围内。文章来源地址https://www.toymoban.com/news/detail-844785.html
到了这里，关于动态规划——最长回文子串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
