LeetCode[5].最长回文子串

Note
关于遍历顺序：
(1)从递推公式中可以看出，长度大于 2 时是根据dp[i + 1][j - 1]是否为true，再对dp[i][j]进行赋值true的。dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：
(2)如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。
所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。
(3)遍历时，j 直接是从 i 开始往后遍历，因为根据 dp数组的定义，j 不可能小于 i ,遍历的图形是一个倒三角形(上宽下尖)

代码：

class Solution {
    public String longestPalindrome(String s) {
        //dp[i][j]的含义是以 i 开头，j 结尾的字符串是否是回文串  默认初始化为 0，即 false
        int dp[][] = new int [s.length()][s.length()];
        //记录最大长度,以及该长度对应的起始位置，以便后续返回最长回文串
        int start = 0,maxl = 0;
        //单个字母一定是回文串
        for(int i = 0;i<dp[0].length;i++){
            dp[i][i] = 1;
        }
        //遍历顺序见注解
        for(int i = dp[0].length-1;i>=0;i--){
            for(int j = i;j<dp[0].length;j++){
                if(s.charAt(i) == s.charAt(j)){
                    //长度为 2 且两字母相同则为回文串
                    if(j-i+1<=2){
                        dp[i][j] = 1;
                    }else{
                        //长度大于2 的话则类似于 bacab,b 相同只用看 aca 是不是回文串即可，即dp[i+1][j-1]
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //更新最长回文串
                if(dp[i][j] == 1 && j-i+1>maxl){
                    maxl = j-i+1;
                    start = i;
                }
            }
        }
        //和 c++的 substr 不太一样，Java 第一个参数是起始位置，第二个位置是结束位置(不包含) c++的第一个参数是起始位置，第二个参数是截取长度
        return s.substring(start,start+maxl);
    }
}

class Solution { public String longestPalindrome(String s) { //dp[i][j]的含义是以 i 开头，j 结尾的字符串是否是回文串默认初始化为 0，即 false int dp[][] = new int [s.length()][s.length()]; //记录最大长度,以及该长度对应的起始位置，以便后续返回最长回文串 int start = 0,maxl = 0; //单个字母一定是回文串 for(int i = 0;i<dp[0].length;i++){ dp[i][i] = 1; } //遍历顺序见注解 for(int i = dp[0].length-1;i>=0;i--){ for(int j = i;j<dp[0].length;j++){ if(s.charAt(i) == s.charAt(j)){ //长度为 2 且两字母相同则为回文串 if(j-i+1<=2){ dp[i][j] = 1; }else{ //长度大于2 的话则类似于 bacab,b 相同只用看 aca 是不是回文串即可，即dp[i+1][j-1] dp[i][j] = dp[i+1][j-1]; } } //更新最长回文串 if(dp[i][j] == 1 && j-i+1>maxl){ maxl = j-i+1; start = i; } } } //和 c++的 substr 不太一样，Java 第一个参数是起始位置，第二个位置是结束位置(不包含) c++的第一个参数是起始位置，第二个参数是截取长度 return s.substring(start,start+maxl); } }