BAT面试算法进阶(6)- 最长回文子串(更新)

学习是唯一的捷径!

一.算法题

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example

Example1:

Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example2: Input: "cbbd" Output: "bb"

二.算法题解读

题目大意:给定一个字符串S,找出S串中最长的回文子串.你可以假设s的最大长度为1000.

解读Example

Example1:

输入: "babad"

输出: "bab"

注意: "aba" 是一个有效答案.

Example2:

输入: "cbbd"

输出: "bb"

三.回文字符串

我们上一篇文分享的不管从时间复杂度还是空间复杂度,都是颇为浪费的? 难道没有更优解决方案?肯定是有的!

四.代码

C++ Code

五.复杂度

时间复杂度: o(N*N) 空间复杂度: O(1)

六.学习建议

大家可以花10分钟左右,将代码的模拟执行一遍.即可明白其过程.明天我们会更新一种另外的解决方案哦.

小编OS:

如有疑问,留言即可.胖C会利用空余时间给大家做一个简单解答的.