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

描述

给定一个字符串str，再给定str的最长回文子序列字符串strlps, 请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。进阶问题比原问题多了一个参数，请做到时间复杂度比原问题的实现低。

输入描述：

输出包含两行，第一行包含一个字符串代表str（1≤lengthstr≤5000）（1≤lengthstr​≤5000）,第二行包含一个字符串，代表strips。

输出描述：

输出一行，代表返回的值。

示例1

输入：

A1B21C
121

输出：

AC1B2B1CA

说明：

str=“A1B21C"，strlps="121"，返回“AC1B2B1CA”或者“CA1B2B1AC”，总之，只要是添加的字符数最少，只返回其中一种结果即可。 

本题同上一题的区别是，本题主动给出了字符串的最长回文子序列是：strlps，根据这个来构建添加最少字符形成的最短回文串。

根据题目：【区间dp-回文子序列-8-1】leet 1312. 让字符串成为回文串的最少插入次数 题解一得知：最短回文串的长度=原串的长度s+(s-最长回文子序列的长度）=2n-m. m=最长回文子序列的长度. 所以char[] ans=new int[2n-m].

根据题目：【区间dp-回文子序列-8-2】添加最少的字符让字符串变为回文字符串得知道构建 ans需要从两边进行。

仍然令字符串str的指针，l=0，r=n-1，ans的指针 i=0，j=ans.length-1，最长回文子序列strlps的指针 s，e

当str[l]==str[r], 则ans的i和j也分别取值s的两端，l++，r--，i++，j--，s++，e--;

当str[l]!=str[r]，则比较str[l]和strlps[s]以及str[r]和strlps[e]的值。

str[r]和strlps[e]右边相同 说明str[l]被最长子序列漏掉了，需要在ans两边取str[l]，左边ans[i]正常取str[l],右边ans[j]需要补充对称相同字符，str左边字符被取用过之后不再取用，所以l++

    public static String minInsertions(String str1, String str2) {
        char[] str = str1.toCharArray();
        char[] strlps = str2.toCharArray();
        int n = str.length;
        int m = strlps.length;

        char[] ans = new char[n + n - m];

        int l = 0, r = n - 1;
        int i = 0, j = ans.length - 1;
        int s = 0, e = m - 1;
        while (i <= j) {
            if (str[l] == str[r]) {
                ans[i] = str[l];
                ans[j] = str[r];
                l++;
                s++;
                r--;
                e--;
            } else {
                if (str[r] == strlps[e]) { 
				//右边相同说明str[l]被最长子序列漏掉了，需要在ans两边取str[l]，左边ans[i]正常取		                   str[l],右边ans[j]需要补充对称相同字符。str左边字符被取用过之后不再取用，所以l++
                    ans[i] = str[l];
                    ans[j] = str[l];
                    l++; //此时不需要处理strlps因为strlps里面不含有str[l]
                } else {
                    ans[i] = str[r];
                    ans[j] = str[r];
                    r--;
                }
            }
            i++;
            j--;
        }
        return new String(ans);
    }

相似题目：

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

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

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

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