描述
所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的,比如"aba"。当然,我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在
要求你,给你一个字符串,可在任意位置添加字符,最少再添加几个字符,可以使这个字符串成为回文字符串。
输入
第一行给出整数N(0<N<100)
接下来的N行,每行一个字符串,每个字符串长度不超过1000.
输出
每行输出所需添加的最少字符数
样例输入
1
Ab3bd
样例输出
2
思路分析:
1.判断字符串前后俩个字符是否相同,如果相同,则删去这俩字符,判断剩余的字符,不需要添加字符。
2.如果不相同,则添加最少的字符的数量 = min((在字符串前添加和末尾一样的字符,删除末尾字符,判断其余字符串),(在字符串后添加和前边一样的字符,删除
前边的字符, 判断其余字符串) ) + 1 ;很容易用递归实现,不过考虑到会超时,可以用数组保存计算过程中的结果,避免不必要的重复计算。
第二种思路:
其实就是最长公共子序列的变种,将原序列str倒置后得到tmp。求出最长公共子序列的长度,则这些就是回文字串,剩下的就是没有匹配的字符的个数。用总长度减去最长公共子序列的长度,就得到需要添加的字符数量。
代码如下:
分享到:
相关推荐
C语言判断回文字符串代码
Python实现最短回文字符串输出
判断回文字符串的C程序,一个简单的小作业,课程中写的,不会的可以参考一下。
判断一个是否是回文字符串。回文字符串是指正序(从左向右)和倒序(从右向左)读都是一样的字符串。 示例1 输入:abc 输出:false 示例2 输入:-121 输出:false 示例3 输入:abba 输出:true 判断是否为回文...
本文实例讲述了Python回文字符串及回文数字判定功能。分享给大家供大家参考,具体如下: 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的。回文数字也是如此。 python2代码如下: def huiwen...
c语言代码写的回文字符串判断, for(i=0;i;) { if(str[i++]!=str[j--]) return 0;
Manacher算法:求解最长回文字符串,时间复杂度为O(N) 回文串定义:“回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。回文子串,顾名思义,即字符串中满足回文性质的子串。
代码实现输入任意字符串,并计算输入字符串最大回文长度,并返回回文字符串。
判断输入的一个字符串是否是回文字符串,当是回文字符串的时候输出该字符串是回文字符创,否则输出该字符串不是回文字符串
ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文...
C++/C回文字符串的实例详解判断输入的字符串是不是回文字符串,正反读一样。.C版#include<stdio>int main(){ char he[100]; char a; int i=0,flag=1; while((a=getchar())!='\n') { he[i]=a; i++; } int n=i; for(i=...
华为机试题目 简单地判断回文字符串的小程序
判断用户输入的随即字符串在去掉空格后是否为回文字符串。
一个简单的判断回文字符串的程序。希望可以给大家一点方便。。
1.任意输入一个数,用两种方法判断该数是不是回文数,像1,323,45254; 方法一,设原数为12,是将输入数进行倒序(21),然后与原数(12)进行比较,若不同则不是回文;...任意输入一个字符串,判断它是不是一个回文字符串
python判断回文字符串
python判断回文字符串
判断一个字符串是否是回文字符串.c