例题:
分析:
先给出以下字符串,找出最长的回文子串
由题可知,最长的回文子串为 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 = 0 && j right - left){left = i;right = j;}}}