添加最少的字符让字符串变成回文串（2）

[编程题]添加最少的字符让字符串变成回文串（2）

热度指数：878 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

输出包含两行，第一行包含一个字符串代表str,第二行包含一个字符串，代表strips。

输出描述:

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

示例1

输入

A1B21C
121

输出

AC1B2B1CA

说明

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

算法知识视频讲解

Java

从极之渊_

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;


public class Main {
    private static String getPalindrome(String str, String strlps) {
        if (str == null || str.equals("")) {
            return "";
        }

        char[] chas = str.toCharArray();
        char[] lps = strlps.toCharArray();
        int strLen = chas.length;
        int lpsLen = lps.length;
        int resLen = 2 * strLen - lpsLen;
        char[] res = new char[resLen];
        int chasl = 0;
        int chasr = strLen - 1;
        int lpsIdx = 0;
        int resIdx = 0;

        while (chasl <= chasr) {
            if (chas[chasl] != lps[lpsIdx]) {
                res[resIdx] = chas[chasl];
                res[resLen - resIdx - 1] = chas[chasl++];
            } else if (chas[chasr] != lps[lpsIdx]) {
                res[resIdx] = chas[chasr];
                res[resLen - resIdx - 1] = chas[chasr--];
            } else {
                res[resIdx] = lps[lpsIdx];
                res[resLen - resIdx - 1] = lps[lpsIdx];
                chasl++;
                chasr--;
                lpsIdx++;
            }
            resIdx++;
        }

        return new String(res);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String strlps = br.readLine();
        System.out.println(getPalindrome(str, strlps));
    }
}

编辑于 2024-03-26 22:02:13 回复(0)