nyoj 37回文串

时间:2023-03-09 08:05:34
nyoj 37回文串

述所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。

输入
第一行给出整数N(0<N<100)
接下来的N行,每行一个字符串,每个字符串长度不超过1000.
输出
每行输出所需添加的最少字符数
dp[i][j]=dp[i+1][j] s[i]==s[j]
              min(dp[i+1][j],dp[i][j+1])+1; (不相等)
先求长度为2的,再求3的,最后长度为l的,就是答案
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scn=new Scanner(System.in);
int len=scn.nextInt();
while(len-->0)
{
String s=scn.next();
int l=s.length();
int dp[][]=new int[l][l];
for(int i=1;i<l;i++)
{
for(int j=0;j<l-i;j++)
{
if(s.charAt(j)==s.charAt(j+i))
{
dp[j][i+j]=dp[j+1][i+j-1];
}
else
{
dp[j][i+j]=Math.min(dp[j][i+j-1],dp[j+1][i+j])+1;
} } } System.out.println(dp[0][l-1]); } } }