【完虐算法】最长回文子串，动态规划，核心关系要领，到底有什么关系？大厂为什么老爱考这些？

零、前言

这几天校招的脚步越来越近，不少小伙伴、朋友最近私信我很多关于校招的问题。后面打算做一期出来，帮助大家避避坑。

另外，好像也有金九银十这回事情也要到来了，最近好多在职小伙伴都在讨论社招的面试题，又是一个跳槽季。

绝大多数是围绕面试，要刷什么题，怎么刷？除了刷题还需要看哪些面经来阻挡八股文似的面试等等…

焦虑、等待、努力拼一下又成了这个时间点常常在程序员人群中看到的一个现象。

关于我自己的话，还是乖乖的再待着，现在考虑的就是和大家一起面对。能提供一些帮助出来。

一、紧凑的脚步

再提一嘴，很多小伙伴知道我在前一段时间组织了一个刷题群，而且在上周的时候送了大家不少资料出来。

一起刷题、一起总结

意在提供尽可能多的信息，让大家少走弯路。因为在我毕业的时候的的确确走了不少弯路。

这个弯路真的不能走，否则，真的是未来几年都弥补不回来的。

在我毕业的那会儿，不知道是校园的信息欠缺还是新校区带给我们比较一个封闭的环境。种种原因吧，居然大多数人不知道各大厂都各自的校园招聘的网站，甚至大多数人不知道官网投简历后，可以线上笔试。

现实是很多人所理解的校园招聘指的是亲自来学校招生的企业。（不过这会儿不一样了）

至今清晰的记得很多学习优秀的同学，由于信息不对称，没有去到他们理想中的企业。

上面的 LeetCode 群，不仅仅是刷题群，也是大家校招讨论的一个场地，我也会在各方面给大家提供我能力范围内的帮助。

回归到一个面试题，是最近几天一个同学遇到的。很有需要拿出来一起总结一些经验出来。

二、快手二面题目

就在前两天的下午，大学隔壁舍友在快手的大数据面试中，被问到一个算法题目，在动态规划思考方式的解法中算是很有代表性的一个题目。

前几天也把动态规划的题目进行了第一步总结，侧重解题方法，如果没有看到过并且对动态规划不通透的建议看一下，这篇文章整整写了一周，个人认为很清晰和详尽。

动态规划终极复盘

朋友碰到的题目是最长回文子串

LeetCode链接是：https://leetcode-cn.com/problems/longest-palindromic-substring/

示例是这样：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

下面详细聊聊这个题目。

同时聊聊是什么原因可以使用动态规划来解决问题，并且用之前写的解题套路解题，来看看。

三、最长回文子串

这个题目解决的方式很多，比如说马拉车算法、中心扩展算法等等…

但动态规划的方式解决这个题目才是最有意思的。刻骨铭心！

动态规划，前几天知乎上有人说这个名字起得太吓人了，应该叫状态记录。试着一句话解释：程序计算过程中，在不断记录过程值的过程中规划求得当前最优值。拗口！具体来看看…

先用一个字符串说点事：s = [ A, B, C, B, A ]

这是一个回文串，但同时可以说明一个很显然的现象：

首先 s[2] 是回文；

如果 s[1] == s[3] 相同，由于 s[2]是回文， 那么，s[1: 3] 必然是回文串；

如果 s[0] == s[4] 相同，由于s[1: 3]是回文， 那么，s[0: 4] 必然是回文串。

即：利用之前记录的状态，来判断当前的状态

也就是说外围的值一样，同时里面已经证实是回文串，那么，此时的字符串一定是回文串。

下面用字符串s =[ B, A, B, A, D ] 详细的长图一步一步讲解最长回文子串的计算流程：

由于要判断是否是回文，那么一定会涉及到从 i 到 j 这个逻辑。

所以，需要一个二维数组来存放状态值。

判断从 i 到 j 的是否是回文这个逻辑，是没有反着来的，仅仅需要二维数组的右上三角区域存储。

另外，使用我们之前 动态规划终极复盘 说过的四步走，除了最后一步优化，其他 3 步骤为：

第 1 步 定义动态数组 dp；

第 2 步 动态方程：dp[i][j] = s[i] == s[j] and dp[i+1][j-1]

如下图，判断当前的状态，一定是依赖于左下角元素；

第 3 步 初始化，对角线一定是 True，其他初始化为 False。

注：当j-i<=2 的时候，只需要判断s[i] == s[j]不需要判断dp[i+1][j-1]。因为当j-i<=2 ，最多就 3 个字符，如果s[i] == s[j]，可推理出肯定为回文。

另外，需要提一点，由于动态方程规则的性质，我们必须要从左到右，从上到下填写表格来记录状态值：

下面，长图预警（建议点开原图）一步一步来看。

同时注意上面所说的，当j-i<=2 的时候，只需要判断dp[i] == dp[j]不需要判断dp[i+1][j-1]，因为当j-i<=2 ，最多就 3 个字符，如果dp[i] == dp[j]，可推理出肯定为回文。

所有的步骤都走过一次，在计算过程中，记录 dp 数组中最后一次出现 True 的 i 和 j，即可得到最长回文子串。

但是在实际代码中，可以利用 dp 数组中为 True 的记录所在的 i 和 j，给出 max_len=j-i+1，然后不断更新 dp 数组为 True 记录所在的 i 和 j，直到取得最大的 max_len。最后用 max_len所在位置的 i和max_len得到最长回文子串。

上图制作不易，感觉还凑合的，给个三连哈…

全部的逻辑从文字到代码都讲解完毕了！下面看看代码，使用 Python 写的，很简洁：

def longestPalindrome(self, s):
    size = len(s)
    if size == 1:
        return s
    # 定义动态数组 dp，同时初始化
    dp = [[False for _ in range(size)] for _ in range(size)]
    for i in range(size):
        dp[i][i] = True

    max_len = 1     # 记录回文串长度
    start = 0       # 记录回文串起始位置
    # 动态方程：dp[i][j] = s[i] == s[j] and dp[i+1][j-1]
    for j in range(1, size):
        for i in range(0, j):
            dp[i][j] = (s[i] == s[j]) and (j - i <=2 or dp[i + 1][j - 1])
            if dp[i][j]:
                if j - i + 1 > max_len:
                    max_len = j - i + 1
                    start = i

    return s[start: start+max_len]

从 j开始，再循环 i循环的原因是根据填写 dp 状态表格顺序！

以上！

全部结束。有人可能会想起优化的点来，嗯。。这个题目用动态规划解决在空间方面其实是没有办法进行进一步优化的，如果有其他优化想法的，群里或者底部留言讨论哈。

四、感恩同行

关于动态规划刷题这个阶段还差一篇 LeetCode 题目复盘总结篇。之前一起刷题的小伙伴们要记得呀！真的很开心能够和大家一起坚持下来，对于在职人员真的不易！

今天这个题目是临时碰到的，对于理解动态规划思想有很不错的指引作用。

代码和本文的文档都在 https://github.com/xiaozhutec/share_leetcode ， 估计半年时间会把各方面题目都完整的记录下来，包括完整的代码和详细的文档说明（都是长图解读，逻辑的每一步都可帮助清晰理解）。

需要的小伙伴可以自行下载代码执行跑起来！方便给个 star 还可行。谢过大家！