题目描述:
输入一个字符串,求出其中最长的回文字串的长度。子串的含义为:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和yyxyy。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应保持原样(在回文串的首部和尾部不要输出多余字符)。输入字符串长度不超过5000,且占据单独的一行。应该输出最长的回文串,如果有多个,输出起始位置最靠左的。
样例输入:Confuciuss say:Madam,I‘m Adam.
样例输出:Madam,I'm Adam.
思路分析:
1.首先将字母全部转换为大写字母(isalpha函数和toupper函数),存入另一个数组。
2.枚举回文串的起点和终点。
3.判断是不是回文串。
第一次代码可以先求出最长回文字串的长度:
这个程序还有一些功能没有完成,但离成功已经不远了-在实际编程中,我们经常先编写一个具备主要功能的程序,再加以完善。我们甚至可以先写一个只有输入输出功能的骨架,但是要确保它正确。这样,每次只添加一点点小功能,而且写一点就测试一下,保证它的正确性。这种方法称为迭代式开发。
现在的任务是输出这个回文串:要求原样输出,并且尽量靠左。输出靠左的条件已经满足了。我们是从左到右枚举的,且只在j - i + 1严格大于max时才更新。这样,就只剩下唯一的问题了:原样输出。
我们可以新开一个数组,用以记录s数组中字母在原数组中的起点和终点,之后输出即可。但是,题目中要求的字符可能多达5000个。则发现,效率太低。TLE。
另一种思路:
枚举回文串的中间位置i,然后不断向外扩展,直到有字符不同。(长度为奇数和偶数处理方式不同)
最终代码如下:
分享到:
相关推荐
这个算法可以应用到文字录入测试的应用中,测试文字录入内容,常用的处理方法是关键字检测发,通过检测word文件中的关键字,可以测出考生操作的大概结果,但是很不准确,利用最长公共子序列算法进行文字录入测试,...
给定字符串s,找到最长子字符串的长度而不重复字符。 示例1:输入:s =“ abcabcbb”输出:3说明:答案为“ abc”,长度为3。 示例2:输入:s =“ bbbbb”输出:1说明:答案为“ b”,长度为1。 示例3:输入:s =...
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串。 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题...
编程求N个非空串的最长公共子串的长度,2;N个串中的字符只会是数字0到9或小写英文字母a到z;每个串非空且最多含100个字符;N个串的长度的乘积不会超过30000。 Input 输入的第1行是一个整数T,表示测试数据的个数(1)...
我们可以构造的最长的回文串是dccaccd, 它的长度是 7。 题解: 方案一:使用ASCII表,英文字母大小写总共占有58个字符,统计字符串中的每个字符出现的次数,放在数组中,再判断每个字符出现的次数有多少个2的倍数,...
对于每组数据,输入数据只有一行,n(n)个字符串用空格分开,每个字符串只含有大写的英文字母,每个字符串长度不大于50。每个字符串中不含有空格。 ----------------------------------------------------------...
五、一个字符串,获取最长的一个单词,如有多个相同长度的单词返回第一个单词。入输入:"hello china"则返回 hello 六、将一个字符里出现最多的字母截取,如,addcbbs变为acs。 七、输入一个整型...
如果当前循环没有找到最大回文字串,则将遍历的回文字串长度--,继续循环 时间复杂度:O(n^3) 空间复杂度:O(1) 07. 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 方法:每次获取剩余整数...
改版:回文字串、多串的LCS等 5、括号序列模型 改版:关灯问题(TSOJ)、charexp(TSOJ)、最大算式等,核心思想在于以串的长度为阶段。 6、递推模型 这类题是属于徘徊在DP与递归之间得一类题,本质是类似于记忆...
五、一个字符串,获取最长的一个单词,如有多个相同长度的单词返回第一个单词。入输入:"hello china"则返回 hello 六、将一个字符里出现最多的字母截取,如,addcbbs变为acs。 七、输入一个整型...
字符分类统计:从键盘输入一行字符串(字符串长度小于等于1000),统计出其中的英文字母、空格、数字和其它字符的个数 题3. 求S=A+AA+AAA+AAAA+….的值,其中,A是0~9范围内的一个数字。输入N和A,其中N表示累加的...
汽水瓶.py,求int型正整数在内存中...字符串反转.py,字符串分割.py,字符串合并处理.py,字符串加密.py,字符串加密2.py,字符串排序.py,字符串运用-密码截取.py,字符串最后一个单词的长度.py,字符个数统计.py,坐标移动.py
2 8 字符串的最长回文子串:Manacher 算法 42 第 3 章 序列 44 3 1 网格中的最短路径 44 3 2 编辑距离(列文斯登距离45 3 3 最长公共子序列 47 3 4 升序最长子序列 49 3 5 两位玩家游戏中的必胜策略 52 第 4 章 数组...
评注:可以用来计算字符串的长度(一个双字节字符长度计2,ASCII字符计1) 匹配空白行的正则表达式:\n\s*\r 评注:可以用来删除空白行 匹配HTML标记的正则表达式:<(\S*?)[^>]*>.*?|*? /> 评注:网上流传的版本太...
最后一句话的长度-容易 之字形转换-中 最小窗口子串-硬 通配符匹配-硬 确定字符串一半是否相同-简单 确定两个字符串是否闭合-中 验证外来字典-轻松 检查两个字符串数组是否等效-简单 编辑距离-困难 文字对齐-困难 ...
设输入的英文短文不超过一行(假设正文最后有“.”结束,以“,”或空格分隔,不出现其他符号),编程将所有单词输出,并求其中最长单词的长度,并将该单词输出。 (4)编写一个程序实现如下功能:有8位裁判为1个...
-------8 习题3 栈和队列------------------------------------------------------------------------------11 习题4 串----------------------------------------------------------------------------------...
getDirName : 根据全路径获取最长目录 getFileName : 根据全路径获取文件名 getFileNameNoExtension : 根据全路径获取文件名不带拓展名 getFileExtension : 根据全路径获取文件拓展名 Fragment 相关 -> ...
锚点及其他“零长度断言” 129 注释和模式量词... 135 分组,捕获,条件判断和控制... 137 高级话题引导... 142 第4章:表达式的匹配原理.... 143 发动引擎... 143 两类引擎... 144 新的标准... 144 正则...
5.4.3 用T-SQL解决最长上升子序列的长度问题 5.5 总结 第6章 子查询、表表达式和排名函数 6.1 子查询 6.1.1 独立子查询 6.1.2 相关子查询 6.1.3 行为不当的子查询 6.1.4 不常用的谓词 6.2 表表达式(Table ...