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，并且只有一个最长回文子串。

例子：

字符串：“cabccba”，最长回文子串为“abccba”。

寻找回文子串，明显不能将当前字符作为回文子串的第一个字符处理，应该将其看做回文子串的对称中心。
回文子串又分为奇数长度和偶数长度两种形式考虑。
奇数长度的回文子串，最小长度为1，以当前字符为中心，向两边辐射，遇到两边不相等或者字符串的首尾边界时，返回长度。
偶数长度的回文子串，最小长度为0，以当前字符和下一个字符为中心，向两边辐射。
有没有办法将以上两种形式，归纳地写成一个方法？其实是可行的，设定寻找字串长度的方法，传进去的入参，有一个对称左值和对称右值，奇数长度时，左值等于右值，以左值和右值为中心，记录扩张次数extendTime和回文长度count（每次加2），在退出方法时，对奇数长度的回文做count-1操作。
在退出方法之后，可以计算出回文开始索引位置startIndex，配合长度count，对原字符串做String.substring()方法，可以返回具体的回文。
在遍历进行到某个程度，可以直接退出，即在遍历过半之后，会出现当前的最大长度，大于接下来可能取到的最大理论值。
注意检查入参，不仅是空判断，题意还规定了最大长度1000的限制。

解题代码：

 public static String longestPalindrome(String s) {

         if (s == null || s.length() > 1000) {

             throw new IllegalArgumentException("Input error");

         }

         char[] array = s.toCharArray();

         // 最大回文子串长度和其开始位置索引

         int maxLength = 0;

         int startIndex = 0;

         for (int i = 0; i < array.length; i++) {

             // 超过字符串一半之后，理论上可能达到的最大长度小于当前的最大长度，直接退出循环

             if (i > (array.length - 1) / 2 && 2 * (array.length - 1 - i) + 1 < maxLength) {

                 break;

             }

             // 分奇偶计算回文长度

             int count1 = extend(array, i, i);

             int count2 = extend(array, i, i + 1);

             int count = Math.max(count1, count2);

             if (count > maxLength) {

                 maxLength = count;

                 // 奇偶的startIndex可以统一成一个表达式

                 startIndex = i - (count - 1) / 2;

             }

         }

         return s.substring(startIndex, startIndex + maxLength);

     }

     // 奇数回文和偶数回文统一处理

     private static int extend(char[] array, int left, int right) {

         // 回文长度和外扩次数

         int count = 0;

         int extendTime = 0;

         // 外扩至超出数组范围

         while (left - extendTime >= 0 && right + extendTime < array.length) {

             // 不对称，直接跳出

             if (array[left - extendTime] != array[right + extendTime]) {

                 break;

             }

             extendTime++;

             count += 2;

         }

         // 奇数回文，最终长度减一

         if (left == right) {

             count--;

         }

         return count;

     }

longestPalindrome

秒客网

No.005：Longest Palindromic Substring

相关文章