01算法回顾
02算法分析
暴力解法:
简单暴力求解,列举所有的子串,判断是否为回文串,保存最长的回文串。简单粗暴,先将两个数组合并,两个有序数组的合并也是归并排序中的一部分。然后根据奇数,还是偶数,返回中位数。简单粗暴,先将两个数组合并,两个有序数组的合并也是归并排序中的一部分。然后根据奇数,还是偶数,返回中位数。
扩展中心
我们知道回文串一定是对称的,所以我们可以每次循环选择一个中心,进行左右扩展,判断左右字符是否相等即可。
由于存在奇数的字符串和偶数的字符串,所以我们需要从一个字符开始扩展,或者从两个字符之间开始扩展,所以总共有 n+n-1 个中心。
03算法总结
时间复杂度从三次方降到了一次,美妙!这里两次用到了动态规划去求解,初步认识了动态规划,就是将之前求的值保存起来,方便后边的计算,使得一些多余的计算消失了。并且在动态规划中,通过观察数组的利用情况,从而降低了空间复杂度。