题解 | #最长回文子串#

动态规划求解最长回文子串

1. 所谓回文子串就是正反读都一样且连续
2. 回文子串具有轴对称
3. 最长回文子串，需要有一个变量来记录满足回文子串时的最大长度
4. 本题是个阉割版本的回文子串，只求了长度，没有求具体的回文子串是什么
5. 所以用额外一个变量记录最大长度时,起始的位置则可以求出具体的回文子串
6. 本代码建议仔细阅读，放在自己的IDE跑跑试试
7. 有任何问题请留言

 *  注意点：
 *  1. maxlen初始应该最少为 1 即没有一个长度为2的回文子串，每个字母都是长度为1的回文子串
 *  2. maxlen 在 dp[i][i+1] = true时, maxlen = 2
 *  3. 当 len > 3时 dp[i][i+len-1]= true 且 len > maxlen 则 maxlen = len;
 */

import java.util.Scanner;

public class test61 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] c = str.toCharArray();
        // TODO 1. 状态容器
        boolean[][] dp = new boolean[str.length() + 1][str.length() + 1];
        int maxLen = 1;
        int starti = 0;
        // TODO 2. len = 1
        for (int i = 0; i <= str.length(); i++) {
            dp[i][i] = true;
        }
        // TODO 3. len = 2
        // 8-2 = 6 => c[i+1] 最多只能到c[6+1]=c[7]
        for (int i = 0; i <= str.length()-2; i++) {
            if(c[i] == c[i+1]){  // i与i+1 长度就是2
                dp[i][i+1] = true;
                maxLen = 2;
                starti = i;
            }else {
                dp[i][i+1] = false;
            }
        }
        // TODO 4. len > 2
        for (int len = 3; len <= str.length(); len++) {
            for (int i = 0; i <= str.length() - len; i++) {
                // 为啥是 i+len-1 因为第3个字符在 c中从下标2开始
                // i 与 i+len-1 就是 len长度
                //  TODO 5. 头与尾相等
                if(c[i] == c[i+len-1]){
                 //   TODO 6. 把 dp（i+1,i+len-1-1) 的状态给 dp[i][i+len-1]
                    dp[i][i+len-1] = dp[i+1][i+len-2];
                }else {
                    dp[i][i+len-1] = false;
                }
                // dp[i][i+len-1] 为 true且 长度 len > maxLen 则重新赋值
                // 这里len 只能 > 3
                if(dp[i][i+len-1] && len > maxLen){
                    maxLen = len;
                    starti = i;
                }
            }
        }

        // 记录当 maxlen 最大时,i的位置 sub(i,i+len)(不包含i+len即为 str(i,i+len-1))
        System.out.println(str.substring(starti,starti+maxLen));
        System.out.println(maxLen);


    }
}