时间限制:1秒

空间限制:32768K

给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢?
输出需要删除的字符个数。

输入描述:
输入数据有多组,每组包含一个字符串s,且保证:1<=s.length<=1000.

输出描述:
对于每组数据,输出一个整数,代表最少需要删除的字符个数。

输入例子1:
abcda
google

输出例子1:
2
2

思路:根据给出的串,与其逆置的串,求出他们之间的最长公共子序列。之后再用总长度减去序列长度,即为答案。

最长公共子序列状态转移方程:

KAU3105)7E4SB{$TRJXUODK.png

代码:

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define MAXN 1010
char *rev(char *s)
{
    int len = strlen(s);
    char *str = new char[len + 1];
    for(int i = len-1; i >= 0; i--)
        str[len-1-i] = s[i];
    str[len] = 0;
    return str;
}
int max(int a, int b)
{
    return a > b ? a : b;
}
int c[MAXN][MAXN];
int main()
{
    char str[MAXN], *str2;
    while(cin >> str)
    {
        int len = strlen(str);
        str2 = rev(str);
        for(int i = 0; i < MAXN; i++)
            c[i][0] = c[0][i] = 0;
        for(int i = 1; i <= len; i++)
        {
            for(int j = 1; j <= len; j++)
            {
                if(str[i-1] == str2[j-1])
                    c[i][j] = c[i-1][j-1]+1;
                else
                    c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
        }
        cout << len - c[len][len] << endl;
    }
    return 0;
}





你可能感兴趣的文章

评论区

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

您好,欢迎到访网站!
  查看权限

«   2019年3月   »
123
45678910
11121314151617
18192021222324
25262728293031