本文主要是介绍Leetcode面试经典150题-5.最长回文子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解法都在代码里，不懂就留言或者私信
class Solution {public static String longestPalindrome(String s) {if(s == null || s.length() == 0) {return null;}//加工字符串，例如abcdcba加工成#a#b#c#d#a#b#c#d#String str = getManacherString(s);char[] strArr = str.toCharArray();int[] pArr = new int[strArr.length];//回文区域的最右边的下一个位置int R = -1;//把回文区域推到R-1的圆心位置，R更新的话C一定要更新int C = -1;//记录最大的递归半径int max = 1;//end用来表示max最大时候的递归范围的右边界int end = -1;for(int i = 0; i < strArr.length; i++) {//R是原来推到的最右位置的下一个位置，R=i的时候，i就在原来的最远区域的外面了//R>i代表i还在原来推到的最远的右边界内//先赋值一个不用验证的范围:如果在R外则最小半径是1，在R外则取Math.min(pArr[2*C - i], R - i)//为什么这个区域不用验证看<https://www.xiaohuazhuo.com/board/656b07678b0e1e0a7cc8784a>//1.如果i在C的递归范围以内（R>i）,分为三种情况//(1) 如果i关于C对称的位置i1的递归左边界在L~R之间，则i的递归半径与i1相同，递归右边界在R之前,递归直径为pArr[2*C-i],这种情况这个值比R-i小//(2) 如果i关于C对称的位置i1的递归左边界在L之前，则i的递归右边界是R，递归半径是R-i，这种情况R-i比pArr[2*C-i]要小//(3) 如果i关于C的对称的位置i1的递归左边界刚好就是L，则i位置的递归右边界至少为R，递归半径至少为R-i，这种情况R-i>=pArr[2*C-i]//这三种情况的最小值都是Math.min(pArr[2*C - i])，前两种情况的递归半径是确定的，第三种情况仍有继续扩大的可能//2如果i在C的递归范围以外(R<=i)则递归半径至少=1是不用证明的，这种情况就是两边都扩不了（该位置自身）//我们可以通过pArr[i]=1这种情况可以想到C+pArr[i]肯定是以R为中心的递归范围的下一个位置pArr[i] = R > i? Math.min(pArr[2*C - i], R - i) : 1;//如果以i为中心的递归范围的左边前一个位置strArr[i+pArr[i]]和右边后一个位置strArr[i-pArr[i]]相等，则递归半径+1while(i+pArr[i] < strArr.length && i - pArr[i] >= 0 && strArr[i+pArr[i]] == strArr[i-pArr[i]]) {pArr[i] ++;}if(pArr[i] + i > R) {R = pArr[i] + i;C = i;}//这里需要写个if，因为要获取end,endif(pArr[i] > max) {max = pArr[i];end = i + pArr[i]-1;}//max = Math.max(max, pArr[i]);}//最大递归范围的终点是end,最大的半径是(max-1)/2，则范围为end - 2*(max-1)~end//end对应原数组的位置就是(end-1)/2,这里注意的是subString这个方法的范围是[start,end)前闭后开的区间//原数组中的每个位置在新的manacher数组中的下标是2*i+1,在新数组中第一个位置为end-2*(max-1)+1，对应的原数组的下标为(end-2*(max-1))/2//(end-2*(max-1))/2=end/2-(max-1)=end/2-max+1//而结束位置为end，对应原数组的位置为(end-1)/2,但是第二个参数是开区间，所以应该写成(end-1)/2 + 1= (end+1)/2return s.substring(end/2-max+1,(end+1)/2);}public static String getManacherString(String s) {char[] sArr = s.toCharArray();char[] strArr = new char[sArr.length * 2 + 1];strArr[0] = '#';for(int i = 1; i < strArr.length; i++) {if((i & 1) == 1) {strArr[i] = sArr[i/2];} else {strArr[i] = '#';}}return String.valueOf(strArr);}}
这篇关于Leetcode面试经典150题-5.最长回文子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
