5. 最长回文子串

2刷。感觉看矩阵不太好理解,还是按原来的。
动态规划假设子问题已经解决,看最后一步。

class Solution {
    //dp[i][j],ss[i...j]是不是回文子串
    //递推
    //dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]
    //注意循环遍历的顺序。
    public String longestPalindrome(String s) {
       char[] ss=s.toCharArray();
       boolean[][] dp=new boolean[ss.length][ss.length];
       int max=0;
       int left=0,right=0;
       for(int i=0;i<ss.length;i++)
           dp[i][i]=true;
       for(int j=1;j<ss.length;j++){//实际上是固定最后一个,变换起点
       //不能是固定起点,变换终点。这也不是解动态规划的思路:看最后一步
           for(int i=0;i<j;i++){//对角线以上的
                if(i+1<=j-1)
                    dp[i][j]=dp[i+1][j-1]&&(ss[i]==ss[j]);
                else{//两个元素
                    dp[i][j]=(ss[i]==ss[j]);
                }
                if(dp[i][j]&&max<(j-i+1)){
                     max=j-i+1;
                     left=i;
                     right=j;
                }
           }
       }
       return s.substring(left,right+1);

    }
}

上一篇:成功解决schedule.ScheduleValueError: Invalid time format


下一篇:12/12每周学习报告12