回文字符串

我就是我 2022-06-11 04:25 311阅读 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 条评论，311人围观）

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

相关阅读

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

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

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

相关回文字符串

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

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

相关回文字符串

最近遇到两个题目，比较有意思，由于两个题目的描述比较相似，在这里就一起说了，做一个比较题目一：给定一个字符串，给该字符串添加一些字符，使其成为一个回文串，求需要添加的最少字

清疚/ 2023年06月02日 09:09/ 0 赞/ 3 阅读

相关【必备算法】字符串（回文问题）：LeetCode题 125. 验证回文串，680. 验证回文字符串 Ⅱ

写在前面，判断是不是回文的逻辑其实很简单，就是借助双指针不断判断首尾相应位置元素是否相等，java模板如下： boolean isPalindrom(String s

浅浅的花香味﹌/ 2022年12月15日 12:53/ 0 赞/ 146 阅读

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

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

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

相关判断回文字符串

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

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

相关字符串-回文判断

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

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

相关回文字符串

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

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

相关验证回文字符串

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

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

相关验证回文字符串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXh

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