题目:
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:如有不正确或提高效率的方法,欢迎留言,谢谢!
原标题:No.005:Longest Palindromic Substring
关键词:string