企业官网建设流程全解析

今天晨起刷题，看到LeetCode每日一题又轮到第5题“最长回文子串”，挺有感触。这道题我第一次做的时候，暴力解法直接超时，后来才一点点把中心扩展、动态规划、Manacher都过了一遍，算是彻底吃透了。今天正好借这轮每日一题，把这道题从暴力到最优解的完整路径拆一遍，也聊聊每种解法背后的思考过程。如果你正在刷LeetCode热门100题，或者刚进字符串专题，这篇文章应该对你有用。另外多说一句，这道题算得上是回文类题目的“母题”，后面遇到的回文链表、回文对、回文子序列，思路多少都跟它沾边。所以今天这篇会讲得细一点，宁可啰嗦，也要让你看完能自己写出来。

1. 今天的题为什么是它：最长回文子串在面试里的分量

1.1 每日一题带来的节奏感，比题目本身更值钱

身边不少朋友问过我，LeetCode每日一题到底值不值得跟。我的结论是：值得，但别把它当成打卡任务，而是当成一个“算法日历”。官方出题不是随机丢一道题过来，它会有意识地覆盖不同数据结构和算法板块。你今天刷数组，明天可能就轮到二分，后天又跳到DP，长期跟下来，你会在不知不觉中把热门题型都过一遍。这种覆盖面，靠自驱刷题其实是很难做到的，因为人总会下意识刷自己擅长的部分，而每日一题没有这种选择性。

最长回文子串被安排在今天的每日一题上，我一点都不意外。字符串专题里，回文是出现率最高的考点之一，而第5题又是回文题的经典代表。这道题的好处在于，它一道题就可以串起多种解题思路：暴力枚举、中心扩散、区间DP、Manacher线性算法。如果你只是想“把题做出来”，那中心扩展法就够了；但如果你想把算法分析能力往上提一档，这道题值得反复做。

1.2 回文这个考点背后的三个层次

面试官为什么这么爱考回文？回文串的判定本身很简单，不就是正着读反着读一样嘛。但一旦问“最长回文子串”，难度就上来了。它至少考三样东西：

• 你能不能分析暴力解法的复杂度，并且说清楚它为什么不可行。
• 你知不知道回文串“去掉首尾还是回文”这个性质，能不能把它变成动态规划的状态转移。
• 你在面对n=1000的约束时，能不能快速判断用O(n^2)的解法够不够，还是需要更激进的优化。

很多题解喜欢直接甩Manacher的模板，一眼看上去很高端，但面试官真正想看的是你的思考路径，而不是背模板。所以今天这篇，我会先讲暴力解法为什么必挂，再讲中心扩展法怎么省掉重复计算，然后讲DP填表顺序里那些坑，最后才聊Manacher这种线性解法到底该不该学。

2. 暴力解法的三维复杂度：回文判断的重复计算到底有多严重

2.1 暴力枚举的完整过程

暴力解法的思路是最直观的：把所有子串都枚举出来，然后逐个判断是不是回文。枚举子串需要两层循环，起点i从0到n-1，终点j从i到n-1，子串的数量是O(n^2)。每拿到一个子串，判断它是不是回文，最坏情况下要从两端往中间逐个比较，这一步又是O(n)。三层套在一起，总复杂度就是O(n^3)。

拿s="babad"来举例。这个字符串的所有子串里，有"bab"、"aba"这种长度为3的回文，也有"a"、"b"这种单字符回文。暴力方法会把每一个子串都检查一遍，哪怕它们之间有大量重复比较。比如判断"bab"的时候要比较s[0]和s[2]，判断"baba"的时候又从头开始比较。两次判断之间没有任何信息共享，这就是暴力解法最吃亏的地方。

2.2 重复计算为什么是致命伤

你可能觉得O(n^3)也不算特别吓人，我们来算笔账。当n=100时，最坏情况要比较大约100万次，这个量级在普通电脑上确实能跑，但LeetCode的字符串长度经常给到1000。n=1000时，O(n^3)意味着大约10亿次字符比较，这就不是“稍微有点慢”了，而是直接打到超时。

更关键的是，这里的重复是非常明显的。假设你已经知道s[1:3]="ab"不是回文，那么在判断s[0:4]="baba"的时候，你其实不需要再重新检查中间的"ab"，因为“去掉首尾之后是不是回文”这个信息，完全可以被内层子串复用。暴力解法没有这种复用机制，所以它做的很多工作都是无用功。

2.3 暴力解的唯一价值是建立基线

我建议你第一遍写这道题的时候，先老老实实写个暴力版本，哪怕知道它提交不过。为什么？因为写暴力能帮你建立一个清晰的基线：你会在编辑器里亲眼看到它怎么超时，然后你才会真正理解为什么后面那些优化是有必要的。如果你一上来就背中心扩展法的代码，你不一定理解它到底省掉了什么。

还有一种情况，暴力解法也不是完全没用。如果面试时遇到一道很偏的题，你一时想不出最优解，先给一个暴力解法，再说明它的复杂度，然后表示“我接下来会尝试用DP优化”，这种沟通方式在面试官眼里是加分项。怕的是你连暴力都写不利索，那后面就无从谈起了。

3. 中心扩展法：把回文当作以某个点为中心的对称扩散

3.1 为什么回文一定有中心

中心扩展法的核心观察是：任何回文串都有一个中心。奇数长度的回文，中心是中间那个字符，比如"racecar"的中心是'e'；偶数长度的回文，中心是中间两个字符之间的空隙，比如"abba"的中心在'bb'之间。理解这两个不同形态的中心，是写出正确代码的关键。

于是枚举中心就成了一个自然的方向。一个长度为n的字符串，一共有n个字符中心，还有n-1个字符间隙中心，加起来就是2n-1个中心。对每个中心，向左右两侧扩展，只要左右字符相等就把半径扩大一格，直到不能扩展为止。过程中记录最长的回文起点和长度。

这个思路本质上就是“从内向外生长”：把每个可能的回文中心都当作种子，看它最远能长多大。它之所以比暴力快，是因为它只用考虑回文这一个维度，不会去检查那些根本不可能成为回文的子串。

3.2 Python实现：中心扩展法的完整代码

def longestPalindrome(s: str) -> str: if not s: return "" start, max_len = 0, 1 def expand(left: int, right: int): nonlocal start, max_len while left >= 0 and right < len(s) and s[left] == s[right]: cur_len = right - left + 1 if cur_len > max_len: max_len = cur_len start = left left -= 1 right += 1 for i in range(len(s)): expand(i, i) # 奇数长度回文，中心是字符本身 expand(i, i + 1) # 偶数长度回文，中心是字符间隙 return s[start:start + max_len]

代码不长，核心就是expand这个辅助函数。每次从左指针和右指针开始，只要不越界且两个字符相等，就同时往左右扩展。如果当前子串比之前记录的最长回文还长，就更新start和max_len。

3.3 两个容易踩的坑

第一个坑是边界判断顺序。while条件里必须先把left >= 0和right < len(s)写在前面，再写s[left] == s[right]。Python的and是从左到右短路求值的，如果先判断字符相等，而left已经小于0，就会直接抛IndexError。这个错误我在初学的时候踩过很多次，后来形成肌肉记忆才改过来。

第二个坑是max_len和start的更新时机。我见过不少同学在expand函数里返回一个子串，然后再跟当前最优值比较，这样写也能工作，但每扩展一次就要切片一次，性能会打折扣。用nonlocal变量在扩展过程中持续更新，是最干净的做法。

中心扩展法的时间复杂度是O(n^2)，空间复杂度是O(1)，因为每个中心最多扩展n次，一共2n-1个中心。实测在n=1000的用例下毫秒级就能出结果，比暴力快了不止一个数量级，对于绝大多数面试场景已经完全够用了。

4. 动态规划填表顺序：为什么必须按子串长度从小到大

4.1 从“去掉首尾”到状态转移

中心扩展法已经能通过所有测试用例了，为什么还要学动态规划？因为回文串有一个很漂亮的性质：如果s[i+1:j-1]是回文，并且s[i]==s[j]，那么s[i:j+1]一定也是回文。

这个性质可以直接改写成状态转移方程。设dp[i][j]表示子串s[i:j+1]是否为回文，那么：

dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

这个方程的意思很简单：一个长回文，去掉首尾两个字符之后，剩下的一定还是回文。反过来，如果首尾两个字符相等，且中间的短子串是回文，那当前这个长子串就是回文。

4.2 初始化：长度1和长度2的边界

转移方程里有个问题，当j-i+1等于2的时候，dp[i+1][j-1]会指向一个不存在的区间，比如dp[0][1]会依赖dp[1][0]。所以在写代码时，要把长度1和长度2的情况单独处理。

长度1的子串，也就是单个字符，一定是回文，所以dp[i][i]=True。长度2的子串，只要两个字符相等，就是回文。代码里可以用一个if length == 2来兜住这个边界，逻辑更清晰。

4.3 填表顺序的坑：为什么不能按i从小到大

这是DP解法最容易出错的地方。如果按i从小到大、j从大到小去枚举，计算dp[0][3]的时候会用到dp[1][2]，而dp[1][2]此时还没被算出来，结果就全错了。

正确的填表顺序是：先枚举子串长度length，从2到n；再枚举起点i；j就是i+length-1。这样在计算长度为length的dp值时，它依赖的dp[i+1][j-1]长度是length-2，已经在上一轮循环里算好了。

说白了，回文DP的依赖方向是“短子串推导长子串”，所以填表顺序必须跟这个依赖方向一致。你不可能先算长的再算短的，那样跟没算一样。

4.4 Python实现：DP解法的完整代码

def longestPalindrome(s: str) -> str: n = len(s) if n < 2: return s dp = [[False] * n for _ in range(n)] start, max_len = 0, 1 for i in range(n): dp[i][i] = True for length in range(2, n + 1): for i in range(n - length + 1): j = i + length - 1 if s[i] != s[j]: dp[i][j] = False else: if length == 2: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] if dp[i][j] and length > max_len: start = i max_len = length return s[start:start + max_len]

代码本身不难，难的是想清楚填表顺序。理解了上面那个“先枚举长度”的坑之后，这段代码基本就是体力活了。

4.5 空间优化：把O(n^2)降到O(n)

看dp转移方程可以发现，计算长度为length的dp值时，只用到了长度为length-2的上一轮结果，再早的结果完全用不上。所以空间上可以优化，不需要保留完整的二维表，用两个一维数组滚动更新即可。

不过我在面试中一般会先写O(n^2)空间的版本，因为可读性最强。如果面试官追问“能不能降低空间复杂度”，我再现场改写成滚动数组。这样既展示了你对DP的理解，又不会一上来就把面试官绕晕。

5. Manacher算法：一个线性解法的读法，以及要不要在面试中写

5.1 预处理：把所有回文统一成奇数长度

Manacher算法的思路，一句话总结就是：利用回文的对称性，避免对每个中心都从头扩展。它首先对字符串做预处理，在每个字符之间以及首尾都插入一个特殊字符，比如#。这样“abc”会变成“#a#b#c#”，原来奇数长度的回文和偶数长度的回文，在预处理串里都变成奇数长度了。

为什么这很重要？因为偶数长度的回文中心落在字符间隙上，处理起来不方便。插入分隔符之后，所有中心都落在一个具体的字符上，代码逻辑就统一了。

5.2 p[i]数组和对称性复用

Manacher算法维护一个数组p[i]，表示以t[i]为中心能扩展到的单侧长度。同时维护center和right，right表示当前所有回文覆盖到的最右边界，center就是覆盖到right的那个回文的中心。

遍历到i时，如果i在right的左边，就可以利用i关于center的对称点mirror来给p[i]一个初始值。因为这两个对称点所处的回文环境是一样的，p[i]至少是min(right-i, p[mirror])。这个初始值省掉了不少重复扩展，然后继续尝试往外扩，看能不能突破right。

这个过程第一次看容易绕晕，我自己的理解方式是把它类比成“照镜子”：你已经知道左边一大段是回文了，右边还没扫描到的地方，跟左边是对称的，那就不用一个个从头比较，直接继承左边已经算好的信息。

5.3 Python实现：Manacher算法的完整代码

def longestPalindrome(s: str) -> str: if not s: return "" t = "#" + "#".join(s) + "#" n = len(t) p = [0] * n center = 0 right = 0 max_center = 0 max_len = 0 for i in range(n): if i < right: mirror = 2 * center - i p[i] = min(right - i, p[mirror]) while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]: p[i] += 1 if i + p[i] > right: center = i right = i + p[i] if p[i] > max_len: max_len = p[i] max_center = i start = (max_center - max_len) // 2 return s[start:start + max_len]

最后一步就是通过max_center和max_len反推出原始字符串里的起点。这里的max_len对应的是原始回文串的长度，start的计算公式在预处理串和原始串之间做了坐标映射，不要自己瞎推，直接按这个公式来最稳。

5.4 到底要不要在面试里写Manacher

我的态度很明确：除非面试官明确考的是字符串算法并且追问“有没有更优解”，否则不要一上来就写Manacher。

原因有两点。第一，Manacher的代码虽然只有30行左右，但逻辑复杂度远高于中心扩展法，面试时手写很容易在p[i]的初始化和边界更新上出bug，写了半天还跑不对，反而影响整体印象。第二，面试官通常更看重你能否清晰表达思路，而不是背模板。中心扩展法O(n^2)的时间复杂度，在n=1000的约束下已经完全够用，面试官不会因为你不写Manacher就否定你。

不过，如果你目标明确，比如在刷竞赛题或者面算法岗，我还是建议理解一下Manacher。它把“利用对称性减少重复计算”这个思想体现得淋漓尽致，这种思想在KMP、Z算法里也能看到，学会了是好事。

6. 从一道题到一类题：热词背后的方法论迁移

6.1 目标和：搜索怎么迭代成DP

LeetCode热门题里有一道“目标和”，跟最长回文子串看起来毫不相关，但底层的进化路径很像。它一开始可以写DFS：每个数字要么加要么减，两条路走到底，看最后能否得到target。直接DFS会超时，因为状态重复太多。这时候你发现可以用记忆化搜索，再进一步简化成01背包DP：把问题转化成“选一部分数字加负号，让总和等于某个值”的计数问题。

对比一下就能发现，回文DP是“去掉首尾”这个性质驱动出来的，目标和DP是“加当前数字还是减”这个选择驱动出来的。共同点是：都要先明确状态是什么，再写转移方程，最后处理边界。这就是方法论迁移的基础。

6.2 爱吃香蕉的狒狒：二分答案的“单调性”

另一道热词里很有意思的题是“爱吃香蕉的狒狒”，LeetCode第875题。它的本质是求一个最小速度k，使得狒狒能在h小时内吃完所有香蕉。这里有个关键观察：k越大，吃完需要的时间越少，这是一个单调函数。所以可以用二分答案，每次判断当前速度是否能在h小时内吃完，然后缩小搜索范围。

Manacher和二分答案之间看起来没什么关系，但它们在“先想清楚怎么表示目标，再设计算法”这一点上是相通的。Manacher先插入#来统一奇偶，二分答案先确定单调性，这些预处理和性质分析，才是解题真正花时间的地方。很多刷题的人一上来就套模板，却忽略了这一步，结果到了变体题就卡住。

6.3 杨辉三角：动态规划最朴素的形态

“杨辉三角”是很多人的DP入门题，它比最长回文子串更简单，但结构非常清晰：第i行的第j个数字，等于第i-1行的第j-1个数字加上第i-1行的第j个数字。这种“上一行推导下一行”的方式，和回文DP的“短子串推导长子串”几乎是同一个套路。

我建议你把这些题放在一起刷，而不是孤立地刷某一道。最长回文子串、目标和、杨辉三角，这三道题看起来毫无关联，但它们都在训练同一件事：找状态、写转移、卡边界。等你把这三个环节变成肌肉记忆，遇到新题就不会慌。

6.4 拿到新题先问自己的三个问题

最后分享一个我自己的习惯。遇到一道没做过的题，我不会急着写代码，而是先问三个问题：

• 状态是什么？我要在一个什么样的表格或维度上做决策。
• 转移是什么？从一个更小的状态，怎么推出当前状态。
• 边界在哪里？初始化哪些值，哪些特殊情况要单独处理。

最长回文子串的状态是“子串是否为回文”，转移是“去掉首尾后是否回文”，边界是“长度1总是回文”。目标和的状态是“当前下标和当前总和”，转移是“加还是减”，边界是“下标走到底时判断总和”。杨辉三角的状态是“当前行当前列的值”，转移是“上一行两个值相加”，边界是“每行首尾都是1”。

这三问想清楚之后，一道题的基本框架就出来了，剩下的就是细节和调试。

刷题这件事，说到底不是比谁背的模板多，而是比谁能在更短的时间里看清问题的结构。最长回文子串这道题之所以被我反复拿出来讲，就是因为它一个题目里塞了好几种结构，从暴力到线性，每一层都能学到点东西。今天这轮每日一题能轮到它，也算是个整理思路的好机会。你如果之前只是草草做了一遍，建议隔两周回来再做一次，不看题解，卡住了再去看。这种做法，比一次刷十道题管用。