字符串变为回文最少添加字符进阶解法

在字符串处理算法中，有一道经典高频面试题：给定一个字符串，允许在任意位置添加字符，要求计算最少添加多少个字符能使整个字符串成为回文串，并输出其中一种合法结果。这道题本身就具备一定挑战性，而其进阶版本额外引入了最长回文子序列字符串（strlps），目标是在已知该子序列的前提下进一步降低时间复杂度。本文将详细拆解这道进阶问题的解法，帮助读者深入理解“剥洋葱”式的高效思路。

题目与进阶要求

原问题：给定一个字符串str，返回在添加字符最少的情况下，使str整体成为回文字符串的任意一种结果。
进阶问题：额外提供str的最长回文子序列字符串strlps，要求设计一种比原问题时间复杂度更低的算法。

该题难度标记为“困难”，但一旦掌握核心思路，就会发现它其实是一个层层剥离的“剥洋葱”过程，直观且高效，适合在面试或竞赛中快速实现。

解题思路详解

如果已拥有最长回文子序列字符串strlps，算法时间复杂度可优化至O(N)。设str长度为N，strlps长度为M，最终回文串的总长度为2×N − M。解法类似于逐层剥洋葱：每次处理当前最外层的一对字符，并填充到结果数组的两端。

以下通过具体例子演示完整步骤：
str = "A1BC22DE1F"，strlps = "1221"。首先创建结果数组res，长度为2×N − M。

洋葱的第0层由strlps[0]和strlps[M-1]组成，即"1...1"。从str最左侧开始查找字符'1'，发现字符'A'位于str第0位，'1'位于第1位，因此左侧第0层洋葱圈外的部分为"A"，记作leftPart。从str最右侧开始查找字符'1'，右侧第0层洋葱圈外的部分为"F"，记作rightPart。将(leftPart + rightPart的逆序)复制到res左侧未赋值的位置，将(rightPart + leftPart逆序)复制到res右侧未赋值的位置，此时res变为"AF..FA"。然后将洋葱的第0层"1"复制到res左右两侧未赋值的位置，res变成"AF1..1FA"。至此，第0层被剥离。

洋葱的第1层由strlps[1]和strlps[M-2]组成，即"2...2"。从str左侧第0层洋葱向右查找'2'，发现左侧第1层洋葱圈外的部分为"BC"，记作leftPart。从str右侧第0层洋葱向左查找'2'，右侧第1层洋葱圈外的部分为"DE"，记作rightPart。同样操作：将(leftPart + rightPart逆序)复制到res左侧，将(rightPart + leftPart逆序)复制到res右侧，res变为"AF1BCED..DECB1FA"。然后复制第1层"2"，res变成"AF1BCED2..2DECB1FA"。第1层剥离完毕，洋葱被完全剥开，最终结果"AF1BCED22DECB1FA"。

整个流程的核心是不断定位当前洋葱层的左、右外部分，将(leftPart + rightPart逆序)填入res左侧，将(rightPart + leftPart逆序)填入res右侧，直至所有洋葱层处理完毕。理解这一逻辑后，代码实现便水到渠成。

完整代码实现（Java）

package live.every.day.ProgrammingDesign.CodingInterviewGuide.String;

/**
 * 添加最少字符使字符串整体变成回文串
 *
 * 【原题】
 * 给定字符串str，可在任意位置添加字符，返回添加字符最少的情况下使str整体为回文串的一种结果。
 *
 * 【进阶题】
 * 给定str及其最长回文子序列字符串strlps，返回添加最少字符使str整体为回文串的一种结果。
 * 进阶问题多了一个参数，要求时间复杂度低于原问题的实现。
 *
 * 【难度】
 * 困难
 *
 * 【解答】
 * 进阶问题解法。
 *
 * 已知strlps后，时间复杂度可降至O(N)。设str长度为N，strlps长度为M，最终回文串长度为2×N - M。
 * 本解法采用“剥洋葱”思想，下面通过示例说明：
 *
 * str="A1BC22DE1F"，strlps="1221"。res长度为2×N - M。
 * 洋葱第0层由strlps[0]和strlps[M-1]组成，即"1...1"。从str最左侧找'1'，发现'A'是str[0]，'1'是str[1]，
 * 因此左侧第0层外部分为"A"，记为leftPart。从str最右侧找'1'，右侧第0层外部分为"F"，记为rightPart。
 * 将(leftPart+rightPart逆序)复制到res左侧，将(rightPart+leftPart逆序)复制到res右侧，res变为"AF..FA"。
 * 再将洋葱第0层复制到res左右两侧，res变为"AF1..1FA"。第0层剥离完毕。
 * 洋葱第1层由strlps[1]和strlps[M-2]组成，即"2...2"。从str左侧第0层向右找'2'，左侧第1层外部分为"BC"，记为leftPart。
 * 从str右侧第0层向左找'2'，右侧第1层外部分为"DE"，记为rightPart。
 * 将(leftPart+rightPart逆序)复制到res左侧，将(rightPart+leftPart逆序)复制到res右侧，res变为"AF1BCED..DECB1FA"。
 * 再将洋葱第1层复制到res左右两侧，res变为"AF1BCED2..2DECB1FA"。第1层剥离完毕，洋葱剥完，返回"AF1BCED22DECB1FA"。
 *
 * 整个过程反复寻找洋葱圈的左、右外部分，将(leftPart+rightPart逆序)填入res左侧，将(rightPart+leftPart逆序)填入res右侧，
 * 直至所有层处理完成。具体实现参见下方getPalindrome2方法。
 *
 * @author Created by LiveEveryDay
 */
public class AddMinCharsMakePalindrome2 {

    public static String getPalindrome2(String str, String strlps) {
        if (str == null || str.equals("")) {
            return "";
        }
        char[] chas = str.toCharArray();
        char[] lps = strlps.toCharArray();
        char[] res = new char[2 * chas.length - lps.length];
        int chasLeft = 0;
        int chasRight = chas.length - 1;
        int lpsLeft = 0;
        int lpsRight = lps.length - 1;
        int resLeft = 0;
        int resRight = res.length - 1;
        int tmpLeft = 0;
        int tmpRight = 0;
        while (lpsLeft <= lpsRight) {
            tmpLeft = chasLeft;
            tmpRight = chasRight;
            while (chas[chasLeft] != lps[lpsLeft]) {
                chasLeft++;
            }
            while (chas[chasRight] != lps[lpsRight]) {
                chasRight--;
            }
            set(res, resLeft, resRight, chas, tmpLeft, chasLeft, chasRight, tmpRight);
            resLeft += chasLeft - tmpLeft + tmpRight - chasRight;
            resRight -= chasLeft - tmpLeft + tmpRight - chasRight;
            res[resLeft++] = chas[chasLeft++];
            res[resRight--] = chas[chasRight--];
            lpsLeft++;
            lpsRight--;
        }
        return String.valueOf(res);
    }

    private static void set(char[] res, int resl, int resr, char[] chas, int ls, int le, int rs, int re) {
        for (int i = ls; i < le; i++) {
            res[resl++] = chas[i];
            res[resr--] = chas[i];
        }
        for (int i = re; i > rs; i--) {
            res[resl++] = chas[i];
            res[resr--] = chas[i];
        }
    }

    public static void main(String[] args) {
        String str = "A1B21C";
        String strlps = "121";
        System.out.printf("The palindrome is: %s", getPalindrome2(str, strlps));
    }
}

// ------ 输出结果 ------
/*
The palindrome is: AC1B2B1CA
*/