一、题目

https://leetcode.cn/problems/longest-palindromic-substring/description/

二、 算法思想

使用动态规划思想解决，如果一个子串是回文的，并且它的左右两边各加上一个字符后仍然是回文的，那么这个子串加上这两个字符后也一定是回文的。因此可以用一个二维数组记录每个子串是否是回文的，然后逐步扩展子串的长度，直到找到最长的回文子串。

假设要判断 s[i…j] 是否是回文的，那么只需要判断 s[i+1…j-1] 是否是回文的，并且 s[i] == s[j]，即可判断 s[i…j] 是否是回文的。因此可以用一个二维数组 dp[i][j] 表示 s[i…j] 是否是回文的，如果是回文的，dp[i][j] 的值为 true，否则为 false。初始化时，单个字符肯定是回文的，因此 dp[i][i] 的值都为 true。

然后逐步扩展子串的长度，如果 s[i+1…j-1] 是回文的，并且 s[i] == s[j]，那么 s[i…j] 也是回文的，即 dp[i][j] = true。最后找到所有 dp[i][j] 为 true 的子串中长度最长的即可。

C++代码中，使用一个二维数组dp来存储每个子串是否为回文串的状态，其中dp[i][j]表示字符串s从下标i到下标j的子串是否为回文串。初始化时，所有状态都为0。
接下来，枚举所有可能的子串，从长度为1到n，依次计算每个子串是否为回文串，更新dp数组和最长回文子串的长度和起始位置。最后返回最长回文子串即可。

Java 代码实现

class Solution {public String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];String res = "";for (int len = 1; len <= n; len++) {    //len是回文子串长度for (int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;    //回文子串的右边界if (len == 1) {         // 单个字符是回文串dp[i][j] = true;} else if (len == 2) {      // 两个字符相等就是回文串dp[i][j] = s.charAt(i) == s.charAt(j);} else {        // 状态转移方程dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j);}if (dp[i][j] && len > res.length()) {   // 更新最长回文子串res = s.substring(i, j+1);}}}return res;}
}

C++代码实现

class Solution {
public:
string longestPalindrome(string s) {int n = s.size();//创建一个n*n的二维矩阵（即一个二维向量），其中每个元素是一个整数。vector> dp(n, vector(n)); // 初始化为0int start = 0, maxLen = 1;// 枚举所有可能的子串，从长度为1到nfor (int len = 1; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1; // 子串右端点if (len == 1) {dp[i][j] = 1; // 单个字符是回文串} else if (len == 2) {dp[i][j] = (s[i] == s[j]); // 两个字符相等就是回文串} else {dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]); // 状态转移方程}if (dp[i][j] && len > maxLen) { // 更新最长回文子串的长度和起始位置start = i;maxLen = len;}}}return s.substr(start, maxLen); // 返回最长回文子串}
};

三、算法时间空间复杂度分析

Java代码

算法的时间复杂度为 O(n2)O(n^2)O(n2)，其中 nnn 是字符串的长度。这是因为算法中使用了一个二维数组 dpdpdp，该数组的大小为 n×nn \times nn×n，且算法需要填充该数组的所有元素。对于每个元素 (i,j)(i,j)(i,j)，需要使用 O(1)O(1)O(1) 的时间计算其值。

算法的空间复杂度也是 O(n2)O(n^2)O(n2)。这是因为算法中使用了一个二维数组 dpdpdp，该数组的大小为 n×nn \times nn×n。除此之外，算法还使用了一个字符串变量 resresres，其长度不超过 nnn。因此，该算法的总空间复杂度为 O(n2)O(n^2)O(n2)。

C++代码

算法的时间复杂度为O(n2)O(n^2)O(n2)，空间复杂度也为O(n2)O(n^2)O(n2)。