5.最长回文子串

给定一个字符串,寻找其中的最长字符子串。

思路:从中间向两侧搜索,对每个字符都从中向外扩散。特别需要注意的是,有可能会存在一种情况,就是中间的是偶数,比如assa,这样就没办法准确识别了。为了解决由回文数的中心不在字符上的情况,需要将由字符扩散变为由同一字符组成的字符串扩散。

升级优化版本:主要思想是没必要跑完整个字符串,当跑到离尾部一定距离的字符时,就算将右边的所有字符都包含进去也不可能比最大的大。这个阈值就是字符串长度减去一半的最大长度。还有一处优化在于当中心不在字符上时,没必要在下一个地方搜索了,直接到不一样的字符上再搜索即可。例如122333221时,如果已经在第一个3上搜索过了,那么后面的3也没必要搜索了,下一个直接到2即可。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容