添加最少字符使字符串总体都是回文字符串

给定一个字符串str，若是能够在str的任意位置添加字符，请返回在添加字符最少的状况下，让str总体都是回文字符串的一种结果。数组

思路：该题能够采用动态规划解决，建立矩阵dp[i][j],若是str[i]==str[j],则dp[i][j]=0,若是str[i]！=str[j]，dp[i][j]=min{dp[i+1][j],dp[i][j-1]}+1;其中矩阵表示添加字符的最少数量。具体代码实现以下所示：code

public class GetPalindromel {
    public 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;
            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;
    }
    public String getPalindromel(String str){
        if (str==null || str.length()<2){
            return str;
        }
        char[] chs=str.toCharArray();
        int[][] dp=getDP(chs);
        char[] res=new char[dp[0][chs.length-1] + chs.length];
        int i=0;
        int j=chs.length-1;
        int resi=0;
        int resj=res.length-1;
        while(i<=j){
            if (chs[i]==chs[j]){
                res[resi++]=chs[i++];
                res[resj--]=chs[j--];
            }else if (dp[i][j-1]<dp[i+1][j]){
                res[resi++]=chs[j];
                res[resj--]=chs[j--];
            }else{
                res[resj--]=chs[i];
                res[resi++]=chs[i++];
            }
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        String str="A1B21C";
        GetPalindromel getPalindromel=new GetPalindromel();
        String palindromel = getPalindromel.getPalindromel(str);
        System.out.println(palindromel);
    }
}

求解dp矩阵的时间复杂度为O(),根据str和dp矩阵求解最终结果的过程为O(N)，因此该问题最终的时间复杂度为O()。字符串

进阶题目：get

给定一个字符串str，再给定str的最长回文子序列字符串strlps，请返回在添加字符最少的状况，让str总体都是回文字符串的一种结果。class

该问题相比较上一题增长了一个指定字符串，借用左神的说法就是采用“剥洋葱”的方法解决，根据给定字符串strlps，一层一层的剥，因为在求解结果的时候只是遍历两个指定的字符串数组，这样的话时间复杂度可加速到O(N)，具体代码实现以下所示：psr

public class GetPalindromel2 {
    public String getPalindromel2(String str,String strlps){
        if (str==null||str.equals(" ")){
            return "";
        }
        char[] chs=str.toCharArray();
        char[] lps=strlps.toCharArray();
        char[] res=new char[2*chs.length-lps.length];
        int chsl=0;
        int chsr=chs.length-1;
        int lpsl=0;
        int lpsr=lps.length-1;
        int resl=0;
        int resr=res.length-1;
        int tmpl=0;
        int tmpr=0;
        while(lpsl<=lpsr){
            tmpl=chsl;
            tmpr=chsr;
            while(chs[chsl]!=lps[lpsl]){
                chsl++;
            }
            while(chs[chsr]!=lps[lpsr]){
                chsr--;
            }
            set(res,resl,resr,chs,tmpl,chsl,chsr,tmpr);
            resl+=chsl-tmpl+tmpr-chsr;
            resr-=chsl-tmpl+tmpr-chsr;
            res[resl++]=chs[chsl++];
            res[resr--]=chs[chsr--];
            lpsl++;
            lpsr--;
        }
        return String.valueOf(res);
    }

    private void set(char[] res, int resl, int resr, char[] chs, int tmpl, int chsl, int chsr, int tmpr) {
        for (int i=tmpl;i<chsl;i++){
            res[resl++]=chs[i];
            res[resr--]=chs[i];
        }
        for (int i=tmpr;i>chsr;i--){
            res[resl++]=chs[i];
            res[resr--]=chs[i];
        }
    }

    public static void main(String[] args) {
        String str="A1BC22DE1F";
        String slp="1221";
        GetPalindromel2 getPalindromel2=new GetPalindromel2();
        String palindromel2 = getPalindromel2.getPalindromel2(str, slp);
        System.out.println(palindromel2);
    }
}