5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 中心扩散法 用dp做缓存

代码语言：javascript复制

class Solution {
    public String longestPalindrome(String s) {
            /**
            采用中心扩散法
            不断看 left  right
            如果    dp[l][r]==true前提得 dp[l-1][r 1]也得是true
             */

             Boolean [] [] dp=new Boolean[s.length() 1][s.length() 1];
             for(int i=0;i<dp.length;i  ){
            for(int j=0;j<dp[0].length;j  ){
                dp[i][j]=false;
                }
             }

             int maxLen=0,start=0,end=0;

             for(int right=1;right<s.length();right  ){//righ不断右移
                 for(int left=0;left<right;left  ){//left不断右移 但要小于right
                       
                     if(s.charAt(right)==s.charAt(left)&&(right-left<=2||dp[right-1][left 1])){ 
                         //小于等于2是因为 一开始没有赋值dp, 所以进行高的时候会有nullPoint 
                         // 所以得弄下  right-left<=2 -> 间距最大为2  相邻  间隔一个 都OK  aa  aba
                         dp[right][left]=true;
                         if(maxLen<(right-left 1)){
                             //跟新最大值 起始下标 结束下表
                             start=left;
                             end=right;
                             maxLen=right-left 1;
                         }
                     }

                 }
             }

             return s.substring(start,end 1);
    }
}

缓存 dp 字符串

0 人点赞