【区间dp-回文子序列-8-2】添加最少的字符让字符串变为回文字符串

描述

给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。

输入描述：

输入包含一行字符串，代表str（1≤lengthstr≤5000）（1≤lengthstr​≤5000）。

输出描述：

输出一行，代表返回的字符串。

示例1

输入：

ABA

输出：

ABA

示例2

输入：

AB

输出：

ABA

备注：

时间复杂度O（n2）O（n2）,空间复杂度O（n2）O（n2）

与上一题：【区间dp-回文子序列-8】leet 1312. 让字符串成为回文串的最少插入次数 不同之处在于本题要求给出字符串，上一题只需要给出次数。

思考：结果字符串的最大长度=字符串长度n+ 最少插入字符次数m，所以ans=new char[n+m].

指针l和r分别指向s第一个和最后1个位置。i 和j 分别指向ans的第一个0和最后1个位置n+m-1。从两边构建ans.

如果s[l] == s[r] 则：ans[i]和ans[j]分别取这两个字符，l，r，i，j都分别前进一步，对应l++，r--，i++，j--.

如果s[l] != s[r]，则ans的i，j指向的位置仍然要设置字符，只是取 l或r 一边的值：即 i++，j--，但是 i和j只能走一个

按照上面题目【区间dp-回文子序列-8】leet 1312. 让字符串成为回文串的最少插入次数 题解二 dp[l+1][r]和dp[l][r-1]，可以知道此时取了最小的一边+1。

所以当dp[l+1][r]>dp[l][r-1]的时候取 s[l,r-1]的dp值 ==> 本次ans设置完了以后，后续得从字符串s[l,r-1]的字符中选择来设置ans。所以本次要用s[r]来设置ans两边位置的值。 ans右边取原值s[r], 左边补充对称的值s[r].

否则取[l+1,r], ==> ans设置完了以后 l++，ans两边要设置 l 对应位置的值

所以有以下代码：

     public static String minInsertions(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[n][n];
        for (int r = 0; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                if (l == r) dp[l][r] = 0;
                else {
                    if (s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1] ;
                    else dp[l][r] = Math.min(dp[l + 1][r], dp[l][r - 1]) + 1;
                }
            }
        }

        int m = dp[0][n - 1];

        char[] ans = new char[n + m];
        int l = 0, r = n - 1;
        int i = 0, j = ans.length - 1;

        while (i <= j) {
            if (s[l] == s[r]) { //后续从s[l+1,r-1]字符串中的字符选择了设置 ans两边的i和j 
                ans[i] = s[l];
                ans[j] = s[r];
                l++;
                r--;
            } else {
                if (dp[l + 1][r] > dp[l][r - 1]) { //取了dp[l][r - 1]值
//后续从s[l,r-1]字符串中的字符选择了设置 ans两边字符，所以本次用s[r]处的字符设置ans两端
                    ans[i] = s[r]; 
                    ans[j] = s[r];
                    r--;
                } else { //取了dp[l+1][r]值
//后续从s[l+1,r]字符串中的字符选择了设置 ans两边字符，所以本次用s[l]处的字符设置ans两端
                    ans[i] = s[l]; 
                    ans[j] = s[l];
                    l++;
                }
            }
            i++;
            j--;
        }
        return new String(ans);
    }

类似题目：

【区间dp-回文子序列-7】leet 516. 最长回文子序列

【区间dp-回文子序列-8-1】leet 1312. 让字符串成为回文串的最少插入次数

【区间dp-回文子序列-8-3】添加最少的字符让字符串变为回文字符串

【区间dp-回文子序列-8-4】SH10 回文数组