NC17题解 | #最长回文子串#

动态规划

• dp[i][j]表示从i到j是否是回文字符串
• 本题动态规划的难点在于数组初始化

//初始化先判断1个字符的, 2个字符的回文状态 再3 4 5...n个字符、、、
//而不是常规的，先从dp[0][0],dp[0][1],dp[0][2]...
//而是 dp[0][0] dp[1][1] dp[2][2] dp[3][3] 
//再是 dp[0][1] dp[1][2] dp[2][3] dp[3][4]
//再是 dp[0][2] dp[1][3]...

• 与常规i，j从0到n循环不同，本题循环是i和j的差值每轮循环在增大

for(int l = 0; l < n; l++){
	for(int i = 0; i + l < n; i++){
    	j = i + l;	//j-i = l(j和i的差值是固定的，作为外层循环的变量值)
    }
}

import java.util.*;


public class Solution {
    /*
     * @param A string字符串 
     * @return int整型
     */
    public int getLongestPalindrome (String A) {
        // write code here
        if(A == null || A.equals("")){
            return 0;
        }
        return com(A.toCharArray());
    }
    public int com(char[] chs){
        int n = chs.length;
        boolean[][] dp = new boolean[n][n];
        int max = Integer.MIN_VALUE;
        //l是子串长度
        //初始化先判断1个字符的, 2个字符的回文状态 再3 4 5...n个字符、、、
        //而不是常规的，先从dp[0][0],dp[0][1],dp[0][2]...
        //而是 dp[0][0] dp[1][1] dp[2][2] dp[3][3] 
        //再是 dp[0][1] dp[1][2] dp[2][3] dp[3][4]
        //再是 dp[0][2] dp[1][3]...
        for(int l = 1; l <= n; l++){
            //i是子串的起始位置
            for(int i = 0; i+(l-1) < n; i++){
                //j是子串的终止位置
                int j = i + l - 1;
                if(l==1){
                    dp[i][j] = true;
                }else if(l == 2){
                    dp[i][j] = (chs[i] == chs[j]?true:false);
                }else{
                    dp[i][j] = (chs[i] == chs[j]) && dp[i+1][j-1];
                }
                if(dp[i][j] && l > max){
                   max = l;
                }
            }
        }
        return max;
    }
}