【力扣】05最长的回文子串
题目链接：https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-100-liked
难度：中等
题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例
-
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。 -
输入: “cbbd”
输出: “bb”
我的答案：
class Solution {
public String longestPalindrome(String s) {
//字符数组
char[] chars = s.toCharArray();
int maxlength = 0;//计数器
int index = 0;//起始下标
for (int i = 0; i < chars.length; i++) {//起始下标i
//结束下标j
for (int j = i; j < chars.length; j++) {
boolean flag = true;//假设是回文串
//计算当前的串长度abbcbba 7
int longs = j - i + 1;
for (int k = 0; k < longs; k++) {//遍历当前串是不是回文串
if (chars[i + k] != chars[j - k]) {
//如果有字符不相等,说明不是回文串
flag = false;
break;
}
}
//如果长度大于之前计数器的值并且是回文串则赋值
if (longs > maxlength && flag) {
//回文串长度
maxlength = longs;
//起始下标
index = i;
}
}
}
//由找到的最长的回文串的起始下标index和长度length,截取
//原字符串返回截取的字符串
return s.substring(index, index + maxlength);
}
}
package test;
/**
* @Author Stringzhua
* @Date 2024/11/8 19:07
* description:
*/
public class test02 {
public static void main(String[] args) {
// String s = "abbcbba";
String s = "abbcbbaaaa";
System.out.println(check(s));
}
public static String check(String s) {
//字符数组
char[] chars = s.toCharArray();
int maxlength = 0;//计数器
int index = 0;//起始下标
for (int i = 0; i < chars.length; i++) {//起始下标i
//结束下标j
for (int j = i; j < chars.length; j++) {
boolean flag = true;//假设是回文串
//计算当前的串长度abbcbba 7
int longs = j - i + 1;
for (int k = 0; k < longs; k++) {//遍历当前串是不是回文串
if (chars[i + k] != chars[j - k]) {
//如果有字符不相等,说明不是回文串
flag = false;
break;
}
}
//如果长度大于之前计数器的值并且是回文串则赋值
if (longs > maxlength && flag) {
//回文串长度
maxlength = longs;
//起始下标
index = i;
}
}
}
//由找到的最长的回文串的起始下标index和长度length,截取
//原字符串返回截取的字符串
return s.substring(index, index + maxlength);
}
}
解题思路
- 暴力解法（Brute Force）
- 遍历字符串的所有子串，判断每个子串是否为回文串。
- 从最长的子串开始遍历，一旦找到回文子串，就返回该子串。
- 时间复杂度： O ( n 3 ) O(n^3) O(n3)，其中 n n n 是字符串的长度。对于每个子串，判断其是否为回文串需要 O ( n ) O(n) O(n) 的时间，总共有 O ( n 2 ) O(n^2) O(n2) 个子串，所以时间复杂度为 O ( n 3 ) O(n^3) O(n3)。
- 空间复杂度： O ( 1 ) O(1) O(1)，只需要常数级别的额外空间。
public class LongestPalindromeSubstring {
public static String longestPalindrome(String s) {
int n = s.length();
if (n == 0) return "";
String longest = "";
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// 剪枝操作，如果当前子串长度小于等于已找到的最长回文子串长度，直接跳过
if (j - i + 1 <= longest.length()) continue;
String substring = s.substring(i, j + 1);
if (isPalindrome(substring)) {
longest = substring;
}
}
}
return longest;
}
private static boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i++)!= s.charAt(j--)) return false;
}
return true;
}
}
- 动态规划（Dynamic Programming）
- 定义状态：设
dp[i][j]表示字符串s从索引i到索引j的子串是否为回文串。 - 状态转移方程：
- 当
i == j时，dp[i][j] = true，单个字符是回文串。 - 当
j - i == 1时，dp[i][j] = (s[i] == s[j])，两个相邻相同字符是回文串。 - 当
j - i > 1时，dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]，即首尾字符相同且中间子串也是回文串。
- 当
- 遍历顺序：从长度为1的子串开始，逐步计算长度更长的子串是否为回文串，先计算
dp[i][i]，再计算dp[i][i + 1]，然后计算长度为3及以上的子串。 - 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)，计算
dp数组需要两层循环，每层循环最多执行 n n n 次。 - 空间复杂度： O ( n 2 ) O(n^2) O(n2)，需要一个二维数组来保存状态。
- 定义状态：设
public class LongestPalindromeSubstring {
public static String longestPalindrome(String s) {
int n = s.length();
if (n == 0) return "";
boolean[][] dp = new boolean[n][n];
String longest = "";
for (int len = 1; len <= n; len++) {
for (int i = 0; i <= n - len; 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] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
}
if (dp[i][j] && len > longest.length()) {
longest = s.substring(i, j + 1);
}
}
}
return longest;
}
}
- 中心扩展法（Expand Around Center）
- 遍历字符串的每个字符，以该字符为中心向两边扩展，判断是否为回文串。
- 考虑两种情况：奇数长度回文串（以单个字符为中心）和偶数长度回文串（以相邻两个相同字符为中心）。
- 时间复杂度： O ( n 2 ) O(n^2) O(n2)，对于每个字符，最多需要向两边扩展 O ( n ) O(n) O(n) 次。
- 空间复杂度：
O
(
1
)
O(1)
O(1)，只需要常数级别的额外空间。
代码实现：
public class LongestPalindromeSubstring {
public static 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) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private static 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;
}
}
- Manacher算法（优化的中心扩展法）
- 预处理字符串，在每个字符前后插入特殊字符（如
#），将奇数和偶数长度的回文串统一处理。 - 使用一个辅助数组
p来记录以每个字符为中心的最长回文半径。 - 利用已经计算的回文半径信息，减少不必要的比较。
- 时间复杂度： O ( n ) O(n) O(n)，虽然有两层循环，但内层循环的总执行次数不超过 O ( n ) O(n) O(n)。
- 空间复杂度：
O
(
n
)
O(n)
O(n)，需要一个辅助数组
p来保存最长回文半径。
- 预处理字符串，在每个字符前后插入特殊字符（如
public class LongestPalindromeSubstring {
public static String longestPalindrome(String s) {
// 预处理字符串
String T = preprocess(s);
int n = T.length();
int[] P = new int[n];
int C = 0, R = 0;
for (int i = 1; i < n - 1; i++) {
int i_mirror = 2 * C - i;
if (R > i) {
P[i] = Math.min(R - i, P[i_mirror]);
} else {
P[i] = 0;
}
// 尝试扩展以i为中心的回文子串
while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
P[i]++;
}
// 如果以i为中心的回文子串扩展后超过了R，更新C和R
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// 找到P中的最大值
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}
private static String preprocess(String s) {
StringBuilder sb = new StringBuilder();
sb.append("$#");
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i));
sb.append('#');
}
sb.append('@');
return sb.toString();
}
}
Manacher 算法的主要思想是通过预处理字符串，使得可以用统一的方式处理奇数长度和偶数长度的回文串。然后利用已经计算的回文半径信息，减少不必要的比较，从而将时间复杂度降低到线性。在上述代码中，preprocess方法用于预处理字符串，在每个字符前后插入特殊字符。然后通过for循环计算每个字符为中心的最长回文半径，并记录最长回文子串的相关信息，最后返回最长回文子串。