声明
今天是LeetCode 简单第409 题,以此作为练习记录,欢迎交流。文中也会给出所参考的文章链接,感谢前辈们的总结。
(手动比心ღ( ´・ᴗ・` ))
题目
给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例 1:
输入:
“abccccdd”
输出:
7
解释:
我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。
正文
疑问:
1、回文串是什么?
回文串是一个正着读和反着读都一样的字符串。以回文中心为分界线,对于回文串中左侧的字符 ch,在右侧对称的位置也会出现同样的字符。例如在字符串 “abba” 中,回文中心是 “ab|ba” 中竖线的位置,而在字符串 “abcba” 中,回文中心是 “ab©ba” 中的字符 “c” 本身。
初步探索:
-
找回文中心:
对于偶数字符串,回文中心是中间竖线,左右字符串对称;
对于奇数字符串,回文中心是中间字符,左右字符串对称;
思路1:
利用字典读取字符串,记录每个字符串出现次数,若是都是偶数就对称放;
若有奇数,将第一个奇数放中间,其余偶数字符串放两边。
怎么放?如何实现
思路2:
总结
添加要改颜色的字体
添加要改颜色的字体
添加要改颜色的字体
添加要改颜色的字体
版权声明:本文为qq_42025376原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。