本题解法很多,可用动态规划 中心扩展法 这里给出一种最快的方法manacher算法
class Solution { public String longestPalindrome(String s) { char[] arr = manacher(s.toCharArray()); int n = arr.length; int[] len = new int[n]; // 数组记录每个点的回文半径 int R = - 1, C = -1, max = 0, start = 0; // R代表当前遍历的回文右边界,C代表当前回文中心,max代表最大长度, for(int i = 0; i < n; i++) { // start记录起点最后返回 len[i] = R > i ? Math.min(len[2 * C - i], R - i) : 1;// 分类讨论当前当前点的最短长度 while(i + len[i] < n && i - len[i] > -1) { // 当前点向两边扩散寻找最长半径 if(arr[i + len[i]] == arr[i - len[i]]) { len[i]++; } else { break; } } if(R < i + len[i]) { R = i + len[i]; C = i; } if(len[i] > max) { max = len[i] - 1; start = (i - max) / 2; } } return s.substring(start,start+max); } public char[] manacher(char[] arr) { // 生成*a*b*c*d*c*b*这样的字符数组,奇数偶数两种长度的回文串都转为奇数类型 char[] res = new char[arr.length * 2 + 1]; int r = 0; for(int i = 0; i < res.length; i++) { res[i] = i % 2 == 0 ? '$' : arr[r++]; } return res; } }