你的位置:首页 > Java教程

[Java教程]No.005:Longest Palindromic Substring


题目:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

官方难度:

Medium

翻译:

给定一个字符串S,找出最长回文子串,你可以假定字符串的最长长度为1000,并且只有一个最长回文子串。

例子:

"cabcbaabcaa"的最长回文子串是"cbaabc"

思路:

1.最长回文子串是对称的,那么在遍历字符串的时候,被遍历的字符串要被当成对称中心而不是子串开始位置来考虑。

2.形如"cbaabc"和"cbabc"都是回文子串,所以需要两次考虑。

解题中可能遇到的困难:

1.如果使用String.split("")的方法,形成的数组第一个元素是空字符串,无论从效率还是使用方面,String.toCharArray()是更优的选择。

2.理论上来说,分析一个字符串的双核对称的情况,需要分左右两种情况考虑,但是实际上这一次的有对称就是下一个字符串的做对称,没必要多做一次分析。

3.由于是从中心往外扩,随时注意可能出现的数组越界问题。

4.在遍历到中心偏后的位置,根据以下可能达到的最长字串的长度和当前最长子串的长度比较,可以少做几次循环。

解题代码:

 1 // 返回一个长度为2的数组,第一位是startIndex,第二位是length 2   private static int[] method(String str) { 3     // str.split("")方法生成的字符串,长度+1,第一个是空字符串 4     char[] array = str.toCharArray(); 5     int maxLength = 0; 6     int startIndex = 0; 7     // 循环中使用,先声明 8     int count1; 9     int count2;10     for (int i = 0; i < array.length; i++) {11       // 超过字符串一半之后,理论上可能达到的最大长度小于当前的最大长度,直接退出循环12       if (i > (array.length - 1) / 2 && 2 * (array.length - 1 - i) + 1 < maxLength) {13         break;14       }15       count1 = singleCore(i, array);16       count2 = doubleCore(i, array);17       // 存在超过最大长度的情况18       if (count1 > maxLength || count2 > maxLength) {19         // 不存在相等情况20         if (count1 > count2) {21           // 单核22           maxLength = count1;23           startIndex = i - (count1 - 1) / 2;24         } else {25           // 双核26           maxLength = count2;27           startIndex = i + 1 - (count2 / 2);28         }29       }30     }31     // 返回结果32     int[] result = new int[2];33     result[0] = startIndex;34     result[1] = maxLength;35     return result;36   }37 38   // 单核处理39   private static int singleCore(int index, char[] array) {40     // 长度计数器41     int count = 1;42     // 扩展次数,单核长度为1自对称,不判断43     int extendTime = 1;44     // 直到外扩超过数组范围,一直循环45     while (index - extendTime >= 0 && index + extendTime < array.length) {46       // 不对称,直接跳出47       if (array[index - extendTime] != array[index + extendTime]) {48         break;49       }50       extendTime++;51       count += 2;52     }53     return count;54   }55 56   // 双核处理,没有必要考虑左和右的问题,因为这一次的右就是下一次的左57   private static int doubleCore(int index, char[] array) {58     // 返回长度59     int count = 0;60     // 右双核的情况,最后一位排除61     if (index != array.length - 1) {62       int extendTime = 0;63       // 双核的出界点的基础是不同的64       while (index - extendTime >= 0 && index + extendTime + 1 < array.length) {65         if (array[index - extendTime] != array[index + 1 + extendTime]) {66           break;67         }68         extendTime++;69         count += 2;70       }71     }72     return count;73   }

View Code

 测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q005.java

LeetCode题目地址:

https://leetcode.com/problems/longest-palindromic-substring/

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!