算法-字符串-5.最长回文子串

一、题目：

二、思路解析 

        1.思路：

                最长子串——动态数组

        2.常用方法：

                a.字符串的截断

res=s.substring(start,end+1);

        3.核心逻辑：

                1.特殊情况：字符串为空或字符串的长度为0

if(s==null||s.length())return "";

                2.一般情况：

                       （1） 采用滑动窗口方法：

                                要素：

                                        a.子串长度，即窗口len

                                        b.窗口开始，start<=size-len

                                        c.窗口结束，end=len+start-1；

                       （2）讨论

                                a.当窗口长度为1，即len==1时，此时该窗口范围的子串都是回文子串

if(len==1){
    dp[start][end]=true;
}

                              b.当窗口长度不为1时

                                        len==2：只需判断两个字符是否相等即可判断是否为会为子串

                                        len>2:除了要判断首尾字符是否相等外，还需要判断除去首尾的子串是否为回文子串

if(len==2&&s.charAt(start)==s.charAt(end)){
        dp[start][end]=true;
}else if(s.charAt(start)==s.charAt(end)&&dp[start+1][end-1]){
           dp[start][end]=true;
}else{
        dp[start][end]=false;
}

简化版：

if(s.charAt(start)==s.charAt(end)&&(len==2||dp[start+1][end-1])){
                        dp[start][end]=true;
                    }
                   else{
                         dp[start][end]=false;
                    }

 三、代码实现    

class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()==0)return "";
        int size=s.length();
        String res="";
        boolean[][]dp=new boolean[size][size];
        for(int len=1;len<=size;len++){
            for(int start=0;start<=size-len;start++){
                int end=start+len-1;
                if(len==1){
                    dp[start][end]=true;
                }else if(len==2&&s.charAt(start)==s.charAt(end)){
                    dp[start][end]=true;
                }else {
                    dp[start][end]=s.charAt(start)==s.charAt(end)&&dp[start+1][end-1];
                }
                if(dp[start][end]&&len>res.length()){
                    res=s.substring(start,end+1);;
                }
            }
        }
        return res;
    }
}