欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode刷题5(最长回文子串)

程序员文章站 2022-05-20 11:42:45
...

题目描述:

给定一个字符串 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);    //返回最大子串
    }
    
}