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

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

A1B21C
121

输出

AC1B2B1CA

说明

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

算法知识视频讲解

查看答案及解析

helloxuanbao

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLEN 5001

int main(void) {
    char str[MAXLEN], strips[MAXLEN], *res;
    scanf("%s%s", str, strips);
    int n = strlen(str);
    int m = strlen(strips);
    res = (char *) malloc(2 * n - m + 1);
    res[2 * n - m] = '\0';
    int l = 0, r = 2 * n - m - 1;
    int ll = 0, lr = 0, rl = n - 1, rr = n - 1;
    int i = 0, j = m - 1;
    while (i <= j) {
        while (str[lr] != strips[i]) lr++;
        while (str[rl] != strips[j]) rl--;
        while (ll < lr) {
            res[l++] = str[ll];
            res[r--] = str[ll++];
        }
        while (rl < rr) {
            res[l++] = str[rr];
            res[r--] = str[rr--];
        }
        ll = ++lr;
        rr = --rl;
        res[l++] = strips[i++];
        res[r--] = strips[j--];
    }
    printf("%s\n", res);
    free(res);
    return 0;
}

发表于 2022-02-09 13:52:04 回复(0)