题目描述
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
样例
样例一:
输入:s = "babad"
输出:"bab"
解释:"aba"同样是符合题意的答案
样例二:
输入:s = "cbbd"
输出:"bb"
动态规划
对于一个子串而言,如果是回文串,那么只要判断首尾的两个字母相同后,新的子串同样是个回文串。
例:字符串”ababa”中,如果已知”bab”是回文串,那么”ababa”一定是回文串。
C++ 代码
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size(); // 字符串长度
int init = 0; // 记录最长回文子串的起始点
int ml = 1; // 记录最大长度
vector<vector<int>> dp(n, vector<int> (n)); // 记录是否满足回文
for (int i = 1; i < n; i ++ )
for (int j = 0; j < i; j ++ )
// 若满足回文条件
if (s[j] == s[i]) {
// 若长度为2或3,则直接判定为回文子串
if (i - j == 1 || i - j == 2) dp[j][i] = 1;
else {
if (dp[j + 1][i - 1] == 0) continue;
dp[j][i] = 1;
}
// 若当前串为回文,并且长度大于最大长度,则更新起始点和最大长度
if (dp[j][i] == 1 && (i - j + 1) > ml) {
ml = i - j + 1;
init = j;
}
}
return s.substr(init, ml);
}
};