回文字符串

我就是我 2022-06-11 04:25 261阅读 0赞

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。

例如：abbc 添加2个字符可以变为 acbbca，也可以添加3个变为 abbcbba。方案1只需要添加2个字符，是所有方案中添加字符数量最少的。

Input

输入一个字符串Str，Str的长度 <= 1000。

Output

输出最少添加多少个字符可以使之变为回文字串。

Sample Input

abbc

Sample Output

2

最少个数==串的长度 - 原串和逆序串的最长公共子串长度

#include<cstdio>
    #include<string>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int dp[1005][1005];
    int main()
    {
        string x,y;
        cin>>x;
        y=x;
        reverse(y.begin(),y.end());
        for(int i=0; i<x.length(); i++)
        {
            for(int j=0; j<y.length(); j++)
            {
                if(x[i]==y[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]);
    //一个意思
    //            int p=0;
    //            if(x[i]==y[j])
    //                p=1;
    //            dp[i+1][j+1]=max(dp[i][j]+p,max(dp[i+1][j],dp[i][j+1]));
            }
        }
        cout<<x.length()-dp[x.length()][y.length()]<<endl;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，261人围观）

还没有评论，来说两句吧...

相关阅读

相关 python最大回文(python回文字符串)

python编程语言输出大写字母回文金字塔 forascinrange(ord('A'),ord('J')): foriinrange(ord('J')-asc-1):

墨蓝/ 2023年09月25日 10:46/ 0 赞/ 70 阅读

相关回文字符串

public class HuiWenTest3 \{ /\\ \ @SERLIN \/ public static void main(String\[\]

分手后的思念是犯贱/ 2023年08月17日 17:14/ 0 赞/ 62 阅读

相关 680. 验证回文字符串 Ⅱ

题目： [680. 验证回文字符串 Ⅱ][680. _] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow

小鱼儿/ 2022年12月07日 12:13/ 0 赞/ 141 阅读

相关判断字符串是否为回文字符串_字符串文字

判断字符串是否为回文字符串 String objects hold [ordered sequences][] of bytes, typically characters,

蔚落/ 2022年12月06日 15:38/ 0 赞/ 181 阅读

相关 680. 验证回文字符串 Ⅱ

> 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。 > > 示例 1: > > 输入: "aba" > 输出: True > 示例 2: >

逃离我推掉我的手/ 2022年10月07日 01:52/ 0 赞/ 138 阅读

相关判断回文字符串

include <iostream> include <stdio.h> using namespace std; bool

旧城等待，/ 2022年08月21日 00:17/ 0 赞/ 173 阅读

相关字符串-回文判断

回文回文是一个正着读和反着读都一样的字符串，如madam、我爱我、abba等。判断回文的两种解法解法1 从字符串的两边向中间判断字符串是否是回文。

偏执的太偏执、/ 2022年07月16日 11:40/ 0 赞/ 210 阅读

相关回文字符串

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符，使之变为回文字符串。例如：abbc 添加2个字符可以变为

我就是我/ 2022年06月11日 04:25/ 0 赞/ 262 阅读

相关验证回文字符串

验证回文字符串给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:

秒速五厘米/ 2022年04月23日 03:30/ 0 赞/ 189 阅读

相关验证回文字符串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

男娘i/ 2021年06月10日 20:38/ 0 赞/ 401 阅读