题目

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：“bb”

方法一：中心扩展法

解题思路

• 遍历字符串s中的每个字符，以每个字符为中心向两侧扩展，找到以当前字符为中心的最长回文子串。
• 同时，考虑回文串长度为偶数的情况，以当前字符和下一个字符为中心向两侧扩展，找到以这两个字符为中心的最长回文子串。
• 在扩展过程中，记录最长回文子串的起始和结束位置。
• 最终返回最长回文子串，可以通过substring方法截取子串。

代码实现

public class Solution {public String longestPalindrome(String s) {if (s == null || s.length() == 0) {return "";}int start = 0;int 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);}// 中心扩展法，返回以left和right为中心的回文子串的长度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;}
}

复杂度

时间复杂度：O(n^2)，其中n为字符串s的长度
时间复杂度：O(1)，因为只使用了常数个变量

方法二：动态规划

解题思路

1. 使用动态规划来解决问题，定义一个二维布尔型数组 dp，其中 dp[i][j] 表示字符串 s 中从索引 i 到 j 的子串是否为回文串。
2. 初始化 dp 数组，当 i 和 j 相等时，表示单个字符是回文串，即 dp[i][i] = true；当s.charAt(i) == s.charAt(j)且 j - i <= 2 时，表示长度为 2 的子串是回文串，即 dp[i][j] = true。
3. 遍历 dp 数组，从长度为 3 的子串开始，依次更新 dp 数组。对于 dp[i][j]，如果s.charAt(i) == s.charAt(j)且 dp[i+1][j-1] 为 true，则表示从索引 i 到 j 的子串是回文串，即 dp[i][j] = true。
4. 在遍历过程中记录最长的回文子串，返回最长回文子串。

代码实现

public String longestPalindrome(String s) {int len = s.length();boolean[][] dp = new boolean[len][len];String longestPalindrome = "";int maxLength = 0;// 初始化长度为1的回文子串for (int i = 0; i < len; i++) {dp[i][i] = true;maxLength = 1;longestPalindrome = s.substring(i, i + 1);}// 初始化长度为2的回文子串for (int i = 0; i < len - 1; i++) {if (s.charAt(i) == s.charAt(i + 1)) {dp[i][i + 1] = true;maxLength = 2;longestPalindrome = s.substring(i, i + 2);}}// 动态规划遍历和更新for (int l = 3; l <= len; l++) {for (int i = 0; i <= len - l; i++) {int j = i + l - 1;if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {dp[i][j] = true;if (l > maxLength) {maxLength = l;longestPalindrome = s.substring(i, j + 1);}}}}return longestPalindrome;
}

复杂度

时间复杂度：O(n^2)，其中 n 是字符串 s 的长度，因为要遍历二维数组 dp
时间复杂度：O(n^2)，需要使用二维数组 dp 来记录状态信息

方法三：Manacher算法

Manacher 算法是一种高效的解决回文子串问题的算法，其时间复杂度为 O(n)，其中 n 是字符串的长度。以下是 Manacher 算法的解题思路、代码实现以及复杂度分析

解题思路

1. Manacher 算法的核心思想是利用回文串的对称性，避免重复的比较，从而实现线性时间复杂度。
2. 首先，将原始字符串进行预处理，将每个字符之间插入一个特殊的字符（如 “#”），以处理偶数长度的回文串。
3. 定义一个辅助数组 P，用来记录以每个字符为中心的回文串的半径长度（包括中心字符）。
4. 初始化辅助数组 P，将每个元素初始化为 1，因为每个字符本身都是一个回文串。
5. 从左到右遍历字符串，利用中心扩展法找到以每个字符为中心的回文串的半径长度，并更新辅助数组 P。
6. 在遍历过程中记录当前找到的最长回文串，并记录其结束位置和长度，以便最后返回结果。

代码实现

public class Solution {public String longestPalindrome(String s) {// 预处理字符串，在字符之间插入特殊字符 "#"String t = preprocess(s);// Manacher 算法核心部分int n = t.length();int[] dp = new int[n]; // 动态规划数组，记录每个字符作为回文中心时的回文半径长度int center = 0; // 当前回文串的中心int right = 0; // 当前回文串的右边界for (int i = 0; i < n; i++) {// 如果当前字符 i 在当前回文串的右边界内，可以利用回文对称性直接计算 dp[i]if (i < right) {int j = 2 * center - i; // i 关于 center 的对称点 jdp[i] = Math.min(right - i, dp[j]);}// 尝试将当前字符 i 向两侧扩展，更新 dp[i]int left = i - (dp[i] + 1); // 当前回文串的左边界int rightBound = i + (dp[i] + 1); // 当前回文串的右边界while (left >= 0 && rightBound < n && t.charAt(left) == t.charAt(rightBound)) {dp[i]++;left--;rightBound++;}// 更新当前回文串的中心和右边界if (i + dp[i] > right) {center = i;right = i + dp[i];}}// 找出最长回文子串int maxLen = 0; // 最长回文子串的长度int centerIndex = 0; // 最长回文子串的中心索引for (int i = 0; i < n; i++) {if (dp[i] > maxLen) {maxLen = dp[i];centerIndex = i;}}// 提取最长回文子串StringBuilder result = new StringBuilder();for (int i = centerIndex - maxLen; i <= centerIndex + maxLen; i++) {if (t.charAt(i) != '#') {result.append(t.charAt(i));}}// 去除预处理时插入的特殊字符 "#"return result.toString();}// 预处理字符串，在字符之间插入特殊字符 "#"private String preprocess(String s) {StringBuilder sb = new StringBuilder();for (char c : s.toCharArray()) {sb.append("#");sb.append(c);}sb.append("#");return sb.toString();}
}

复杂度

时间复杂度: O(n)，其中 n 是输入字符串的长度
空间复杂度: O(n)，因为需要使用额外的动态规划数组来保存每个字符

总结

1. 中心扩展法：遍历字符串的每个字符，将其作为回文串的中心，向两侧扩展，判断扩展的字符是否相同，记录扩展的长度，最后找到最长回文子串。时间复杂度为O(n^2)，空间复杂度为O(1)。

2. 动态规划法：利用回文串的动态规划性质，通过动态规划数组记录每个字符作为回文中心时的回文半径长度，避免重复计算，从而找到最长回文子串。时间复杂度为O(n^2)，空间复杂度为O(n)。

3. Manacher算法：利用回文串的对称性，通过动态规划的方式避免重复计算，从而在线性时间内找到最长回文子串。时间复杂度为O(n)，空间复杂度为O(n)。

综上所述，中心扩展法是简单但效率较低的方法，动态规划法通过优化中心扩展法减少了重复计算，而Manacher算法则是最优的方法，具有线性时间复杂度。在实际应用中，可以根据具体情况选择合适的方法来解决寻找最长回文子串的问题

黑咖啡社区