力扣4 （自看

上题上题：

给你一个字符串 s，找到 s 中最长的回文子串

这道题是纯正算法题，需要经过数学方法推算然后产生各种不同的方法，核心就是，如果字符串的第i和j位相等，那i到j是否为回文就受i+1和j-1控制（假设j>i）,所以就需要从ij相邻的情况开始考虑，逐步延申，借助动态规划思想，在每次遍历过程中完成对最大回文串的搜索，还有一些基本的特判在里面，比如s是1个字符的情况。

首先是我最爱（不是）的暴力破解，

class Solution {
    public String longestPalindrome(String s) {
        int len;
        len= s.length();
        boolean huiwen[][] = new boolean[len][len];
        int L=2;   //搜索间隔长度
        int i,j;   //左右标
        char target[] = new char[len];
        target = s.toCharArray();
        String maxhuiwen="";

        if(len==1){
            return s;
        }
        //初始化判别数组
        for(i=0 ; i<len ; i++){
            huiwen[i][i]=true; //所有元素自己能组成最小回文
        }

        maxhuiwen=s.substring(0,1);

        for(; L<=len; L++){   //间隔从相邻开始，间隔逐渐变大 每次对比i与i+L-1的值，
                                   //若相等则huiwen[i][i+l-1]为true
            for(i=0 ; i<len ; i++){    //左边界，他不可能到达s的len位置;
                j = i+L-1;    //根据间隔和左边界推算右边界
                if(j>=len){    //超出边界
                    break;
                }
                if(target[i]==target[j]){
                    if(L!=2)
                        huiwen[i][j]=huiwen[i+1][j-1];  //当前条件的情况满足，则只需让他的上一个情况满足即可
                    else if(L==2){
                        huiwen[i][j]=true;              //即为相邻情况
                    }
                }else{
                    huiwen[i][j]=false;
                }

                if(huiwen[i][j] && j-i+1>maxhuiwen.length()){
                    maxhuiwen=s.substring(i,j+1);
                }
            }
        }
        return maxhuiwen;
    }
}

暴力破解思路简单，使用枚举法解决，但问题是时间复杂度和空间复杂度太高，空间复杂度上，因为创建了一个n方大小的布尔二维度数组，时间上，因为是枚举遍历 所以都是O(n^2)，那么有什么思路可以简化呢，小改一下枚举的思想，从中心位置开始入手（分为奇数和偶数两种情况），也就是下面的代码：

class Solution {
    public String longestPalindrome(String s) {
        int start = 0;
        int end = 0;
        int len = s.length();

        for(int i=0 ; i<=len-1 ; i++){
            int len1 = expendfindlarger(s,i,i); //奇数回文情况
            int len2 = expendfindlarger(s,i,i+1);  //偶数回文情况

            int larger = len1>len2?len1:len2;
            if(larger > end-start){
                start=i - (larger - 1) / 2;
                end=i + larger/2;
            }
        }

        return s.substring(start,end+1);
    }
    
    int expendfindlarger(String s, int left, int right){
        while(true){
            if(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
                left--;
                right++;
            }else{
                break;
            }
        }
        return right-left-1;
    }
}

这样就吊多了，在时间和空间上都进行了很大程度的优化，几乎也没有冗余判断的出现，最后时间和空间都打败了88%（舒服了）

明天噶油！

最后

以上就是瘦瘦吐司为你收集整理的力扣4 （自看的全部内容，希望文章能够帮你解决力扣4 （自看所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。