字符串正读和反读完全一样时,称为回文串.通过在字符串开头或结尾添加一定数量的字符使字符串变为回文串。
现给出长度n的仅包括大写字母的字符串s,请问至少添加多少字符,使之成为回文串。
例如
输入:
3
ABC
输出:
2
一下三个标签,到底需要什麽语言啊?
从第二个字符开始检查,以该字符为中心,将字符串分为两侧,检查字符少的一侧,是否在另一侧形成回文。一直检查到倒数第二个字符,记录其中回文最长的,最后看还多出几个字符,答案就是几。如果没有找到这样的字符,那么答案就是整个字符串长度
C
#include<bits/stdc++.h>
using namespace std;
char s[1010],t[1010];
int dp[1010][1010];
int main()
{
scanf("%s",s);
int l=strlen(s);
for(int i=0,j=l-1;i<l;i++,j--)
t[i]=s[j];
for(int i=0;i<l;i++)
for(int j=0;j<l;j++)
if(s[i]==t[j])
dp[i+1][j+1]=dp[i][j]+1;
else
dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
printf("%d\n",l-dp[l][l]);
}
JAVA
import java.util.Scanner;
public class Main {
/*1、基础:
dp[i][j]:表示str[i...j]最少添加几个字符使得str[i...j]是回文串
时间复杂度O(N^2),空间复杂度O(N^2)
* */
public static 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;//两个字符情况 一个为0
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;
}
//根据dp和str得到新的字符串 时间复杂度O(N)
public static String get1(String str) {
if (str == null || str.length() < 2) {
return str;
}
char[] chas = str.toCharArray(); //str转字符数组
int[][] dp = getDP(chas);
char[] res = new char[chas.length + dp[0][chas.length - 1]]; //返回的结果
int i = 0;
int j = chas.length - 1;
int l = 0;
int r = res.length - 1;
while (i <= j) {
if (chas[i] == chas[j]) {
res[l++] = chas[i++];
res[r--] = chas[j--];
} else if (dp[i][j - 1] < dp[i + 1][j]) {//
res[l++] = chas[j];
res[r--] = chas[j--];
} else {
res[l++] = chas[i];
res[r--] = chas[i++];
}
}
return String.valueOf(res);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
String res = get1(str);
System.out.println(res);
}
}
是只能在左或者右添加,还是左右同时都能加