星空网 > 软件开发 > 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.在遍历到中心偏后的位置,根据以下可能达到的最长字串的长度和当前最长子串的长度比较,可以少做几次循环。

解题代码:

No.005:Longest Palindromic SubstringNo.005:Longest Palindromic Substring
 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

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

外贸企业如何解决客户不提货现象:https://www.ikjzd.com/articles/139555
你知道商标还没有注册就使用,风险有多大吗?:https://www.ikjzd.com/articles/139556
全球外贸资讯 1.4:https://www.ikjzd.com/articles/139557
亚马逊店铺美国站的注册流程和费用:https://www.ikjzd.com/articles/139558
前所未有!新冠疫苗运输带来“意外之财”!但…:https://www.ikjzd.com/articles/139559
亚马逊测评是什么?:https://www.ikjzd.com/articles/139560
无锡旅游景点竹海 - 无锡的竹海:https://www.vstour.cn/a/363178.html
5月贾汪好玩的地方 贾汪哪有好玩的地方:https://www.vstour.cn/a/363179.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流