圣狐资讯
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
此题是一道比较经典的字符串题目，可以使用中心扩展算法或者动态规划算法进行求解。
中心扩展算法：
其中一种常见的解法是基于中心扩展的思想，具体步骤如下：
1.对于字符串s的每个字符，以该字符为中心向左右两侧扩展，找到以该字符为中心的最长回文子串。
2.遍历完所有字符后，比较所有最长回文子串的长度，找到其中长度最长的一个即可。
时间复杂度：O(n^2)，空间复杂度：O(1)
动态规划算法：
建立一个 n * n 的矩阵 dp，其中 dp[i][j] 表示 s 中从 i 到 j 这段子串是否为回文串。
若 dp[i][j] 为 true，则说明 s 的子串 s[i:j] 为回文串。
状态转移方程为 dp[i][j] = dp[i+1][j-1] && s[i] == s[j]，即 s[i:j] 为回文串，当且仅当 s[i+1:j-1] 为回文串且 s[i] == s[j]。
时间复杂度：O(n^2)，空间复杂度：O(n^2)
具体实现细节可以参考下面的代码实现。
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
String ans = "";
for (int i = 0; i < n; i++) {
// 找到以 i 为中心的最长回文子串
int left = i, right = i;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if (right - left - 1 > ans.length()) {
ans = s.substring(left + 1, right);
}
// 找到以 i 和 i+1 为中心的最长回文子串
left = i;
right = i + 1;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
if (right - left - 1 > ans.length()) {
ans = s.substring(left + 1, right);
}
}
return ans;
}
}
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
String ans = "";
for (int l = 0; l < n; l++) {
for (int i = 0; i < n; i++) {
int j = i + l;
if (j >= n) {
break;
}
if (l == 0) {
dp[i][j] = true;
} else if (l == 1) {
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] && l + 1 > ans.length()) {
ans = s.substring(i, j+1);
}
}
}
return ans;
}
}
