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

5. 最长回文子串 mark

程序员文章站 2022-03-11 11:59:06
题目截图自官方代码class Solution { public String longestPalindrome(String s) { //即使写到这份上,"aaaa"还是只能输出"aaa"。自己失败了。 // 很多判断条件,但显然这样是不行的。。。。。 // int n=s.length(); // int tempMax=0; // StringBuffer res=ne...

题目

截图自官方

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

相关标签: LeetCode相关