leetcode刷题5（最长回文子串）

题目描述：

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

通过答案：

方法一：暴力求解（会超时）

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        int max=0;
        String c="";
        for(int i=0;i<len;i++){          //分别判断每一个子串是否为回文串
            for(int j=i+1;j<=len;j++){
                String substr=s.substring(i,j);
                if(isHuiwenchuan(substr)&&substr.length()>max){
                    max=substr.length();     
                    c=substr;            //取长度最长的子串
                }
            }
        }
        return c;
    }
    public boolean isHuiwenchuan(String s){        //判断是否为回文串
        int len=s.length();
        for(int i=0;i<len/2;i++){
            if(s.charAt(i)!=s.charAt(len-i-1)){
                return false;
            }
        }
        return true;
    }
}

方法二:

class Solution {
    public String longestPalindrome(String s) {
        char arr[]=s.toCharArray();     //将字符串转化为数组
        int max=1;                  //最长初始值为1，至少有一个字符
        int len=arr.length;
        int low,hight;
        int beign=0;
        if(len<2)return s;     //若字符串长度为一，直接返回
        for(int i=0;i<len;i++){
            low=i-1;
            hight=i;
            //跳过相同的字符，此串必为回文
            while(hight+1<len&&arr[hight]==arr[hight+1])hight++;
            i=hight++;     //i从相同字符的下一个开始记录
            while(low>=0&&hight<len&&arr[low]==arr[hight]){     //从中间向两边扩展
                hight++;
                low--;
            }
            if(hight-low-1>max){
                max=hight-low-1;
                beign=low+1;    //子串开始下标
            }
        }
        return  s.substring(beign,beign+max);    //返回最大子串
    }
    
}