题目介绍：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000 s 仅由数字和英文字母组成
涉及的数据结构和算法：
动态规划、中心扩展法
下面是使用动态规划和中心扩展法两种方式实现最长回文子串的
动态规划解法：
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
String res = "";
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
if (dp[i][j] && (res.equals("") || j - i + 1 > res.length())) {
res = s.substring(i, j + 1);
}
}
}
return res;
}中心扩展法解法：
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start + 1) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}解题思路：
本题可以使用动态规划和中心扩展法两种方式来实现。
动态规划解法：
我们可以定义一个二维数组 dp，其中 dp[i][j] 表示 s 中以 i 开头、以 j 结尾的子串是否为回文子串。如果 s[i] == s[j] 且 s[i+1:j-1] 是回文串，那么s[i:j] 也是回文串。根据这个递推关系，我们可以使用动态规划来求解最长回文子串。具体地，我们从长度较短的子串开始枚举，每次枚举的时候根据已经计算好的状态来推导新的状态，最终得到最长回文子串的长度和起始位置。
中心扩展法解法：
我们可以枚举每个可能的回文中心，然后用两个指针分别向左右两边扩展，直到两个指针指向的字符不相同为止。具体地，回文中心可能是一个字符，也可能是两个字符（例如 “abba” 的中心是 “bb”），因此一共有 n + n - 1 = 2n - 1 个回文中心需要枚举，其中 n 是字符串 s 的长度。
扩展知识点：
本题中使用了动态规划和中心扩展法两种算法来解决最长回文子串的问题。在实际应用中，我们需要根据具体问题来选择不同的算法来解决问题。此外，回文串是一种非常常见的字符串特性，我们需要熟练掌握如何判断一个字符串是否为回文串，以及如何求解最长回文子串等问题。
总结：
本题使用动态规划和中心扩展法两种方式来实现最长回文子串的求解，时间复杂度分别为 O(n^2) 和 O(n^2)，空间复杂度均为 O(n^2)。在实际应用中，我们需要根据具体问题来选择不同的算法来解决问题。
文章评论