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.

Example1: 输入: "babad" 输出: "bab" 注意: "aba" 是一个有效答案. Example2: 输入: "cbbd" 输出: "bb"

回文字符串

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

代码

复杂度

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

学习建议

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

算法面试系列文章：

BAT面试算法进阶(1)--两数之和

BAT面试算法进阶(2)- 无重复字符的最长子串(暴力法) BAT面试算法进阶(3)- 无重复字符的最长子串(滑动窗口法) BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化+ASCII码法) BAT面试算法进阶(5)- BAT面试算法进阶(5)- 最长回文子串(方法一) BAT面试算法进阶(7)- 反转整数 BAT面试算法进阶(8)- 删除排序数组中的重复项 BAT面试算法进阶(9)- 三维形体投影面积 BAT面试算法进阶(10)- 最长的斐波那契子序列的长度(暴力法) BAT面试算法进阶(11)- 最长的斐波那契子序列的长度(动态规划法) BAT面试算法进阶(12)- 环形链表(哈希表法)