例题:
分析:
先给出以下字符串,找出最长的回文子串
由题可知,最长的回文子串为 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")); // bab System.out.println(longestPalindrome("cbbd")); // bb System.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; } } }
猜你喜欢
网友评论
- 搜索
- 最新文章
- 热门文章