题解 | #添加最少的字符让字符串变为回文字符串（1）#

import java.util.Scanner;
public class Main {

    /*1、基础：
    dp[i][j]：表示str[i...j]最少添加几个字符使得str[i...j]是回文串
    时间复杂度O(N^2),空间复杂度O(N^2)
    * */
    public static int[][] getDP(char[] str) {
        int[][] dp = new int[str.length][str.length];

        for (int j = 1; j < str.length; j++) {
            dp[j - 1][j] = str[j - 1] == str[j] ? 0 : 1;//两个字符情况  一个为0
            for (int i = j - 2; i > -1; i--) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp;
    }

    //根据dp和str得到新的字符串   时间复杂度O(N)
    public static String get1(String str) {
        if (str == null || str.length() < 2) {
            return str;
        }
        char[] chas = str.toCharArray();  //str转字符数组
        int[][] dp = getDP(chas);
        char[] res = new char[chas.length + dp[0][chas.length - 1]];  //返回的结果
        int i = 0;
        int j = chas.length - 1;
        int l = 0;
        int r = res.length - 1;
        while (i <= j) {
            if (chas[i] == chas[j]) {
                res[l++] = chas[i++];
                res[r--] = chas[j--];
            } else if (dp[i][j - 1] < dp[i + 1][j]) {//
                res[l++] = chas[j];
                res[r--] = chas[j--];
            } else {
                res[l++] = chas[i];
                res[r--] = chas[i++];
            }
        }

        return String.valueOf(res);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String res = get1(str);
        System.out.println(res);
    }
}