5. 最长回文子串 mark

题目

截图自官方

代码

class Solution {
    public String longestPalindrome(String s) {
        //即使写到这份上，"aaaa"还是只能输出"aaa"。自己失败了。
        // 很多判断条件，但显然这样是不行的。。。。。
            // int n=s.length();
            // int tempMax=0;
            // StringBuffer res=new StringBuffer();
            // if(s.length()==0){
            //     return ""; 
            // }
            // if(s.length()==1){
            //     return s;
            // }
            // for(int i=1;i<=n-1;i++){
            //     int left=i-1,right=i+1;
            //     if(s.charAt(left)==s.charAt(i)&&tempMax<2){
            //              res.append(s.charAt(left ));
            //              res.append(s.charAt(i));
            //              tempMax=2;

            //     }
            //     while(left>=0&&right<n&&s.charAt(left)==s.charAt(right)){
            //          if(right-left+1>tempMax){
            //              res=new StringBuffer();
            //            for(int j=left;j<=right;j++){
            //                res.append(s.charAt(j));
            //                tempMax=right-left+1;
            //            }
            //          }
            //          left--;
            //          right++;
            //     }
            // }
            // if(tempMax==0){
            //     return String.valueOf(s.charAt(0));
            // }
            // return res.toString();




    // 官方解法
// 动态规划注重一个状态转移。一定要找出这状态转移方程。同时在边界情况处特殊处理。
    int n=s.length();
    boolean [][] dp=new boolean [n][n];
    char[] t=s.toCharArray();
    for(int i=0;i<n;i++){
    dp[i][i]=true;
    }
    if(s.length()<2){
        return s;
    }
    int begin=0;
    int maxLength=1;
    // 竖着填表格。
    for(int j=1;j<n;j++){
        for(int i=0;i<j;i++){
            if(t[i]==t[j]){
                // 处理边界
                if(j-i<2){
                    dp[i][j]=true;
                }else{
                    dp[i][j]=dp[i+1][j-1];
                }
            }else{
                dp[i][j]=false;
            }
        if(dp[i][j]&&j-i+1>maxLength){
            begin=i;
            maxLength=j-i+1;
        }

        }
    }
    // substring是左闭右开的索引。第一次用错了
    return(s.substring(begin,begin+maxLength));
    
    }
}

 

本文地址：https://blog.csdn.net/qq_40941016/article/details/109277227