本文主要是介绍最长回文子串（Leetcode5），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
例题：
分析：
先给出以下字符串，找出最长的回文子串
由题可知，最长的回文子串为 bcbabcb , 长度为7。
我们可以利用 中心开发思想 寻找最长回文子串，简单说就是以一个字符为中心点，由中心点向两边扩散，如果两边的字符相等，则继续扩散，直至两端的字符不相等，此时就找到了最长回文子串的左右边界（left，right）。
根据数组的遍历顺序，一开始以字符b为中心点，并记录此时回文子串的长度，如果后续找到了更长的回文子串，则替换之前的长度。如下图所示：
遍历数组一个一个往后找中心字符。
在这里发现字符b两端的字符相等，扩大范围。此时回文长度更新为3。依次类推....
但是在这里我们还遗漏了一种情况，我们只考虑了中心字符为奇数的情况， 中心字符为偶数 的情况未必比 中心字符为奇数 的长度短。
比如一开始以字符b和c作为中心点，向两边扩散。但这样显然不行，因为b、c不一样，必须找到两个一样的字符作为中心点。如下图：
注意：以两个字符作为中心点的时候，i不要遍历到数组末尾元素，否则会索引越界。
代码实现：
public class LongestPalindromeLeetcode5 {public static void main(String[] args) {System.out.println(longestPalindrome("babad")); // babSystem.out.println(longestPalindrome("cbbd")); // bbSystem.out.println(longestPalindrome("a")); // a}static int left;static int right;public static String longestPalindrome(String s) {left = 0;right = 0;char[] chars = s.toCharArray();for (int i = 0; i < chars.length - 1; i++) {extend(chars, i, i); //一个字符作为中心点extend(chars, i, i + 1); //两个字符作为中心点}return new String(chars, left, right - left + 1);}/*** 中心开发方法* @param chars 要遍历的字符数组* @param i 中心点索引* @param j 中心点索引*/public static void extend(char[] chars, int i, int j){//遇到相同字符则向左右两边扩散while(i >= 0 && j < chars.length && chars[i] == chars[j]){i--;j++;}//已经不是回文了，需要把i和j拉回边界i++;j--;if(j - i > right - left){left = i;right = j;}}
}
这篇关于最长回文子串（Leetcode5）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
