LeetCode 5 — 区间DP&&中心拓展算法

题目描述

最长回文子串

思路1

由于 \(reverse()\) 的时间复杂度是 \(O(N)\)，因此暴力肯定是不行的。

\(dp\) 的思路：如果 \(s[l..r]\) 是一个回文串，那么我们可以立马得知 \(s[l-1,…,r+1]\) 是否是回文串。

也就是说我们可以由小区间得到大区间。

典型的区间 \(dp\) 啊。

思路2

中心拓展算法：

我们可以枚举字符串的每个点为中心，从这个点开始向两头拓展，如果拓展之后的两头边界仍然相同，说明是回文串，否则结束拓展。

因为如果当前不是回文串，继续拓展下去的话肯定仍然不是。

时间复杂度为 \(O(N^2)\)

虽然和 \(dp\) 的时间复杂度级别是相同的，但是该算法的常数更小，每次拓展是拓展两个元素，而 \(dp\) 每次是一个元素。

原文地址：http://www.cnblogs.com/ALaterStart/p/16852281.html