每日一练：最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

题目要求：

给你一个字符串 s，找到 s 中最长的 回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解法-1 动态规划 O(N^2)：

        思路与每日一练：回文子串-CSDN博客相同，不再赘述。

class Solution {
public:string longestPalindrome(string s) {int n = s.size();vector<vector<int>> dp(n);for(int i = 0;i < n;i++)dp[i].resize(i+1);string ret = s.substr(0,1);for(int i = 1;i < n;i++){for(int j = 0;j <= i;j++){if(s[i] == s[j]){if(i == j)dp[i][j] = 1;else if(j == i-1)dp[i][j] = 2;elsedp[i][j] = dp[i-1][j+1]?dp[i-1][j+1]+2:0;if(ret.size() < dp[i][j])ret = s.substr(j,i-j+1); }}}return ret;}
};