Java数据结构与算法(最长回文子串中心扩散法)

前言

回文子串是练习数据结构和算法比较好的使用场景，可以同时练习到双指针、动态规划等一些列算法。

实现原理

中心扩散算法实现。这里定义最长回文子串长度的大小为maxLen，起点位置为0.

奇数个数为中心点和偶数个数为中心点分别计算回文长度大小。注意while退出条件为不匹配回文子串，计算长度时需回退right和left。此时长度计算公式为(right-1)-(left+1)+1

得到最长回文长度大小后再计算起点位置。i-(maxLen-1)/2

具体代码实现

class Solution {public String longestPalindrome(String s) {int maxLen=1;int begin=0;char[] charArray=s.toCharArray();for(int i=0;i<charArray.length-1;i++){int oneNum=validCicle(charArray,i,i);int twoNum=validCicle(charArray,i,i+1);int max=Math.max(oneNum,twoNum);if(maxLen<max){maxLen=max;begin=i-(maxLen-1)/2;}}return s.substring(begin,begin+maxLen);}public int validCicle(char[] charArray,int left,int right){while(left>=0&&right<charArray.length){if(charArray[left]==charArray[right]){left--;right++;}else{break;}}return (right-1)-(left+1)+1;}
}

QA:待定