美文网首页
最长回文子串

最长回文子串

作者: ztao | 来源:发表于2017-11-23 23:44 被阅读0次

Given a string s, find the longest palindromic substring in s.

You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

如果事先知道子串长度,可以从左右往里判断字符是否相等,可本题无法事先得知子串长度。

于是将遇到的字符当作“最中间”向外扩展成了比较合理的选项。开始考虑的是分为奇偶回文,如例子中的两种情况。后来看到一种更简洁的方法,每次把所有和最中间字符相同的字符都略去,等于看成“最中间”所有相等的字符(如果有)看作一体,这样就省去来判断奇偶的步骤。另外注意到,如果剩余的字符串长度不超过当前最长回文长度的一半,就可以提前跳出循环了。

另外,字符串类的题,还是用 C++ 的 string 写的方便,以后的算法题打算用C语言 + C++ string 来写,省去一些低级的字符处理。

相关文章

  • 最长回文子串

    最长回文子串——Manacher 算法 1. 问题定义 最长回文字符串问题:给定一个字符串,求它的最长回文子串长度...

  • 字符串算法

    最长公共前缀 最长回文串 最长回文子序列 最长公共子串 反转单词顺序列 反转字符串 字符串转数字 IP-int互转

  • 打卡-最长回文子串

    最长回文子串(中等)

  • 最长回文子序列

    该问题区别于最长回文子串,子串必须是连续的,而子序列则可以跳跃,例如AABCAA的最长回文子串为AA,但是它的最长...

  • Manacher算法

    最长回文子串问题# 给定一个字符串,找出最长的回文子串,如"waabwswbfd",则最长子串为bwsb. 中心试...

  • 最长回文子串问题—Manacher算法

    最长回文串问题是一个经典的算法题。 0. 问题定义 最长回文子串问题:给定一个字符串,求它的最长回文子串长度。如果...

  • LeetCode 第647题:回文子串

    1、前言 2、思路 此题与最长回文子串很像,只不过那个是求最长的回文子串,而这个是求回文子串的数目。但是他们的解法...

  • C语言实现求最长回文子串

    最长回文子串的概念 回文串是指正序和反序都一样的字符串,例如:Str1 = "AbbA",则Str1的最长回文子串...

  • Manacher's Algorithm算法分析Java

    Manacher's Algorithm俗称马拉车算法,对于求字符串中最长回文子串效率极高。 在求最长回文子串的时...

  • Manacher 算法学习笔记

    前言 给定一个字符串,求出其最长回文子串。例如:s="abcd",最长回文长度为 1;s="ababa",最长回文...

网友评论

      本文标题:最长回文子串

      本文链接:https://www.haomeiwen.com/subject/zootbxtx.html