leetCode 5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
回文就是无论正反都是该字符串它两边对称相等

我先放我的吧，防止你们看完不看我的了时间比较长竟然达到了五秒之多还好这道题没有时间要求确实遍历实在是太长了

public String longestPalindrome(String s) {
        String kk="";
        if(s.trim().length()<=1){
            return s;
        }
        for(int i=1;i<s.length()+1;i++){
            for(int j=0;j+i<s.length()+1;j++ ){
               String str = s.substring(j,j+i);
               if(str.equals(new StringBuilder(str).reverse().toString())){
                    kk=str;
                    break;
               }

            }
        }
        return kk;
    }

我的思路呢就是从0-2开始遍历一直遍历到结束，然后利用StringBuilder的字符串取反功能取反如果相同就将其附给要返回的字符串。因为每个长度碰到第一个就会break所以返回的均是该长度下第一个字符串但是无奈不仅遍历次数多，每次还要切割创建StringBuilder对象时间到达了五秒

然后通过之后当然是要看第一名代码了真的是太厉害了

6MS完成了该题光是看他代码就得理解一会的了

public String longestPalindrome(String s) {
    if (s == null)
         throw new IllegalArgumentException();
    if (s.length() < 2)
         return s;
         char[] arr = s.toCharArray();
         int[] ret = new int[2];//回文字符串的首和尾  前闭后开区间
         for (int i = 0; i < arr.length; i++) {
              i = loop(arr, i, ret);
         }
              return s.substring(ret[0], ret[1]);
    }

private static int loop(char[] arr, int low, int[] ret) {
    int high = low;
    while (high < arr.length - 1 && arr[high + 1] == arr[low])//判断相等字符串回文最长是多少
    high++;
    int res = high;

    while (low >= 0 && high < arr.length && arr[low] == arr[high]) {
//因为回文所以从同一位置分开是对称的  如果该位置减一位等于该位置加一位就表示是回文
//如果一直有对称相等的 就说明该字符串未达到最长 就继续-- ++
//该判断语句 如果碰到自减或自增到字符串边界则返回 或者 不等返回  此时均是在当前起始位置字符最长的回文
         low--;
         high++;
    }
    if (high - low - 1 > ret[1] - ret[0]) {
         ret[1] = high;
         ret[0] = low + 1;
     }
         return res;
}

6MS的大佬