BAT面试算法进阶(5)- 最长回文子串(方法一)

算法题

• 题目

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"

回文字符串

找到字符串的最长公共子串

一般开发者,能想到的最快速的方法,就是找到"最长公共子串".

"反转S并成为S',找到S和S'之间的最长公共子串.它也必须是最长的回文子串"

注意: 如果我们并不是所有的最长公共子串,就一定是最长回文子串.

所以,如果只是单纯的查找最长公共子串方法,是不可行的.但是,如果去修改这个问题?

思路:

在我们找到一个最长的公共子串候选者时,我们检查子串的索引是否与反向子串的原始索引相同.如果是,那么尝试更新到目前为止发现的最长的回文.如果没有,我们就跳过这个,寻找下个候选回文子串.

动态编程解决方案

• 如果子串 Si...Sj 是回文,则定义P[i,j]为真,否则为假
• 所以,P[i,j] <-- (p[i+1,j-1] 和 Si = Sj);

复杂度

时间复杂度:O(N*N）

空间复杂度:O(N*N）

代码

C Code

学习建议

尝试画图->阅读代码

• 算法并不是1+1=2.很多时候需要大家拿好纸笔思考才能感受到它的魅力之处!
• 此次附上小编学习的时候草稿! 大家也一起吧....

算法面试系列文章：

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