字符串最长回文子串java

在 Java 中寻找字符串中最长回文子串是一个经典的算法问题。以下是解决该问题的一种常见思路及其实现方法。 ### 回文的概念 回文是指从前往后读和从后往前读都相同的字符序列，例如“aba”、“racecar”。 --- ### 解题思路 我们可以采用 **中心扩展法** 来求解最长回文子串的问题： 1. 每个位置的字符都可以作为潜在回文的「中心」。 2. 对于每个中心点，向两边扩展，检查是否对称。 3. 需要注意的是，回文可能是奇数长度（如 "aba"），也可能是偶数长度（如 "abba"）。因此需要分别考虑这两种情况。 时间复杂度：O(n^2)，其中 n 是字符串的长度；空间复杂度：O(1)。 --- ### 实现代码 ```java public class LongestPalindrome { public String longestPalindrome(String s) { if (s == null || s.length() < 1) 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 maxLen = Math.max(len1, len2); // 更新最大回文子串的位置 if (maxLen > end - start) { start = i - (maxLen - 1) / 2; end = i + maxLen / 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; // 计算回文长度 } public static void main(String[] args) { LongestPalindrome lp = new LongestPalindrome(); System.out.println(lp.longestPalindrome("babad")); // 输出 "bab" 或 "aba" System.out.println(lp.longestPalindrome("cbbd")); // 输出 "bb" } } ``` --- ### 示例分析 对于输入 `babad`： - 起始遍历第 0 位 `'b'`，得到单字母回文 `"b"`； - 继续遍历第 1、2 位等，发现更长的回文 `"bab"` 或 `"aba"`。 最终返回任意一种符合条件的结果即可。 --- ### 总结 通过上述实现，我们能够高效地找到给定字符串中的最长回文子串。如果还有其他需求可以进一步优化，比如动态规划或 Manacher 算法（线性时间 O(n) 的解决方案）。