摘要：这一题作为中等难度，常规解法对于大多数人应该都没有难度。但是其中也有超难的解决办法，下面我们就一起由易到难，循序渐进地来解这道题。

题目：给你一个字符串 s，找到 s 中最长的回文子串。

这一题作为中等难度，常规解法对于大多数人应该都没有难度。但是其中也有超难的解决办法，下面我们就一起由易到难，循序渐进地来解这道题。

01、暴力破解法

对于大多数题目来说，在不考虑性能的情况下，暴力破解法常常是最符合人的思维习惯的。

比如这道题，求一个字符串中最长的回文子串，那么我们只需要把字符串中所有可能的子字符串都判断一下是不是回文串，并找出长度最长的不就行了嘛。

这里需要三层循环，第一层和第二层循环组织出所有可能的子字符串，第三层循环判断是否为回文串。

而判断一个字符串是否为回文串，也很简单，只需要从字符串两端开始判断首尾字符是否相等，如果相等继续向字符串中心方向前进继续比较下一个首尾字符是否相等，直到比较完所有字符，如果都相等则为回文串。其核心思想是由外向内，逐一比较。

具体代码如下：

时间复杂度：两层for循环O(n^2），for 循环里边判断是否为回文串O(n），所以时间复杂度为O(n^3）。

空间复杂度：O(1），常数个变量。

02、暴力破解法优化（动态规划法）

要想优化暴力破解法，我们要先找到它到底有什么问题。它的时间复杂度之所以这么高，是因为有大量的重复计算，可能文字描述不够直观，下面我们先用二维表展示一个字符串的所有子字符串的组合情况，然后再在这个表中看判断是否为回文串时哪些子字符串被重复判断。

如上图在字符串abcde中，在判断其子字符串bcd是否是回文串时，作为字符串bcd已经计算过了，同样的其子字符串c，作为字符串也已经计算过了，其他的沿着箭头方向都是表示存在重复计算的地方。

到这里我们的优化方案就有了，我们可以把已经计算过的存下来，这样下次用到的时候直接拿过来用而不用再计算了。

既然我们通过图就发现了一些规律，我们不妨再深入思考一下，为什么会这样？

如果我们基于暴力破解法中判断是否为回文串的算法定义回文串，那么可得：

P(i,j)=P(i+1,j-1)&&S[i]==S[j]

可以理解为如果一个字符串是回文串，那么去掉首尾字符后子字符串依然是回文串。反过来如果子字符串是回文串并且其首尾一个字符相等，那么这个字符串整体也是回文串。

我们再对上图斜对角上加些辅助线，如果我们按所有子字符串的长度分类，则会发现长度为3的依赖长度为1的，长度为5的依赖长度为3的，长度为4的依赖长度为2的。如下图：

长度为1本身就是回文串，长度为2的如果两个字符相等则为回文串，那么所有长度大于等于3的都可以通过长度为1和2的计算出来。

到这里整个算法思路就出来了：先计算长度为1和2的子字符串并存入二维数组，然后基于此二维数组继续计算长度为3、4、5……。

具体代码如下：

时间复杂度：O(n^2），即为两层for循环组成的所有子字符串情况。

空间复杂度：O(n^2)，即存储已计算子字符串结果需要的空间。

这个算法还有一个专有名称：动态规划，我们这里之所以没有突出去讲，是想把整个解题思路展现出来，掌握好了基础解题能力，我们才能做总结，而这个解法的总结就可以概括为动态规划，这是一种通用的思想，后面会经常用到。

03、中心扩展法

上面的优化虽然时间复杂度降下来了，但是空间复杂度上升了，我们继续想想有什么其他方法呢？

上面的方法判断是否为回文串的核心思想是由外向内，那我们是否可以换个思路——从内向外呢？这就是中心扩展法的核心思想。

在暴力破解法中，我们需要两层循环表示任何一种子字符串排列，而且中心扩展法核心思想是通过一个中心点向两边扩展也就天然只需要一层循环即可表示探测所有字符的情况。

由中心往两边扩展是对称的，而回文串长度可以是奇数也可以是偶数，因此我们在中心扩展时就需要分奇偶两种情况来处理。

到这里我们可以大致梳理一下整体逻辑了：

（1）依次循环处理字符串的每个字符，向两边扩展；

（2）每次扩展分奇偶两种情况处理；

（3）计算出最大长度并保留；

（4）重复（2）、（3）直至所有字符处理完成；

具体实现代码如下：

时间复杂度：O(n^2)。

空间复杂度：O(1)。

此方法虽然时间复杂度没变，但是空间复杂度大大降低。这也给了我们继续优化的动力。

下一章节我们将详细讲解次题的马拉车解法。

来源：IT规划师