刷题刷到 LeetCode Hot 100第5题“最长回文子串”几乎是绕不开的一道题。它不像两数之和那样一上来就能想到暴力解也不是那种看一眼就知道要用堆或者哈希表的套路题。这道题考察的是对字符串问题的理解深度同样是找子串你能不能从O(n³)优化到O(n²)再进一步想到O(n)的线性解法。我当初刷这道题的时候先后踩过遍历顺序的坑、边界处理的坑也一度觉得马拉车算法是面试官拿来炫技的。但真正把这个题吃透之后再看其他字符串相关的动态规划题思路会清晰很多。这篇文章就把我对这道题的理解、四种解法的实现细节、以及实习和面试中实际考察过的点一次性讲清楚适合刚接触动态规划的同学也适合准备面试想系统过一遍Hot 100的人。1. 题目定位与暴力解法的效率瓶颈1.1 读懂题目回文子串的本质先来回顾一下题目本身。给定一个字符串s要求找出其中最长的回文子串。所谓回文就是正着读和倒着读都一样比如bab、abba甚至单个字符a也算回文。这里有个特别容易混淆的概念子串和子序列。子串必须是连续的一段字符而子序列可以不连续。题目说的是子串所以像abcba中的aba跳过c这种不连续的方案不能算数必须是原字符串中连续截取的一段。这个区别决定了解法思路完全不一样找最长回文子序列用的是另一套动态规划而找最长回文子串则可以从中心扩散的角度去考虑。还有一个细节值得提前注意回文长度可能是奇数也可能是偶数。奇数长度的回文以一个字符为中心例如aba的中心是b偶数长度的回文以两个字符之间的空隙为中心例如abba的中心在bb之间。这两种情况在实现时需要分别处理很多bug就出在这里。1.2 暴力解法为什么O(n³)不可行拿到这道题最直接的想法是枚举所有子串判断每个子串是不是回文记录最长的那个。听起来很简单但算一笔复杂度账就明白了。一个长度为n的字符串子串的个数大约是n(n1)/2个也就是O(n²)个。对每个子串判断是否是回文又要扫描一遍最坏情况是O(n)。两者相乘整体时间复杂度是O(n³)。当n是1000的时候操作次数在十亿级别在LeetCode上直接超时。写一段伪代码感受一下def longestPalindrome(s): n len(s) max_len 1 start 0 for i in range(n): for j in range(i, n): sub s[i:j1] if sub sub[::-1] and j - i 1 max_len: max_len j - i 1 start i return s[start:startmax_len]这段代码逻辑完全正确但性能很差。问题出在哪里判断回文的时候每次都从头开始比较而前面已经算过的信息完全没有被利用。这也引出了优化的核心思路如何减少重复计算。中心扩展法是减少重复计算的第一种手段动态规划是第二种马拉车算法则是把计算信息复用到了极致。2. 中心扩展法最直观的O(n²)方案2.1 核心思路从中心向两边扩散中心扩展法的想法非常朴素回文串的特点是对称的那我随便找到一个中心向两边同时扩展只要左右字符相等就继续扩直到不相等为止。这样就能找到以该中心为对称点的最长回文子串。问题的关键是中心有多少个。很多初学者以为中心就是字符串里的每个字符也就是n个。但别忘了偶数长度的回文中心在两个字符之间比如abba它的中心在b和另一个b中间。因此总共有2n - 1个中心n个是字符本身n - 1个是字符之间的间隙。这个“间隙也是中心”的理解是中心扩展法实现最重要的点。处理间隙中心时可以统一用一种方法从left和right开始向两边扩展奇数中心时left i, right i偶数中心时left i, right i 1。两种情况合在一起就是两个循环分别处理。代码如下def expandAroundCenter(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return left 1, right - 1 def longestPalindrome(s): if not s or len(s) 1: return start, end 0, 0 for i in range(len(s)): left1, right1 expandAroundCenter(s, i, i) # 奇数长度 left2, right2 expandAroundCenter(s, i, i 1) # 偶数长度 if right1 - left1 end - start: start, end left1, right1 if right2 - left2 end - start: start, end left2, right2 return s[start:end1]每个中心向两边最多扩展n/2次中心总数是2n - 1所以总时间复杂度是O(n²)空间复杂度是O(1)。对比暴力的O(n³)这是一个质的飞跃。2.2 奇偶长度的统一处理技巧我在第一次写中心扩展法的时候犯过一个低级错误只处理了奇数长度的情况导致cbbd这种测试用例返回的结果是b而不是bb。原因就是没有处理偶数长度的回文中心。后来我习惯把中心扩展的逻辑封装成一个独立函数返回的是回文串的左右边界外层只需要比较长度并更新最值。这样的好处是逻辑清晰不容易漏掉某一类中心。还有一个小技巧边界条件要特别注意left 0和right len(s)否则很容易越界。返回的时候while循环退出是因为不满足条件了所以真正回文的区间是(left1, right-1)这个细节也容易搞错。另外如果你想验证自己的实现是否正确可以用几个边界测试用例空字符串应该返回空串a单个字符应该返回aaa应该返回aaab应该返回a或b都正确babad结果可以是bab或aba都是合法的。这些小用例覆盖了奇偶长度和边界情况能快速暴露实现中的问题。3. 动态规划用状态转移降低重复计算3.1 状态定义与转移方程推导中心扩展法的思路是从中心往外扩而动态规划的思路恰好相反从短的回文串往长的方向推。核心思想是如果一个子串是回文并且它左右两边的字符相同那么扩展出来的新子串也一定是回文。定义一个二维布尔数组dp[i][j]表示字符串从下标i到下标j的子串s[i..j]是否是回文。状态转移方程是dp[i][j] (s[i] s[j]) and dp[i1][j-1]意思是如果s[i] s[j]并且内部的s[i1..j-1]是回文那s[i..j]就是回文。这里有一个非常重要的边界细节当子串长度小于等于2时dp[i1][j-1]这个状态可能不存在或者没有意义。比如s[i..j]长度为2时i1 j-1中间是空串空串可以视为回文长度为3时中间只有一个字符单个字符一定是回文。所以通常把长度小于等于2的情况单独处理当j - i 2时只要s[i] s[j]dp[i][j]就直接为真。完整代码如下def longestPalindrome(s): 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 j in range(1, n): for i in range(j): if s[i] s[j]: if j - i 2 or dp[i1][j-1]: dp[i][j] True if j - i 1 max_len: max_len j - i 1 start i return s[start:startmax_len]3.2 遍历顺序的坑与空间优化动态规划实现里最容易踩的坑就是遍历顺序。很多人习惯了两层循环都从头遍历但这里会发现一个问题计算dp[i][j]的时候需要用到dp[i1][j-1]也就是说需要先知道左下方那个格子的值。如果你按照i从前往后、j从前往后的顺序遍历计算dp[i][j]时dp[i1][j-1]可能还没有被计算出来。解决办法是改变遍历顺序外层循环遍历右边界j内层循环遍历左边界i保证在计算较长的子串之前较短的子串已经计算完毕。更直观的理解是先算长度短的子串再算长度长的子串。因为dp[i1][j-1]对应的子串长度比dp[i][j]短2只要外循环按长度递增来遍历就一定能保证依赖的状态已经先被算出来。上面的代码就是按j从1到n-1遍历i从0到j-1遍历。这样每次计算dp[i][j]时dp[i1][j-1]已经在上一轮算好了因为j-1 j。说到空间优化dp[i][j]实际上只依赖于dp[i1][j-1]也就是只依赖一行的数据。所以理论上可以用一维数组滚动更新把空间复杂度从O(n²)降到O(n)。但要注意滚动数组的时候遍历方向要反过来否则会覆盖掉还没用到的旧数据。相比中心扩展法O(1)的空间复杂度动态规划在空间上反而更大这也是为什么很多实际场景中更倾向于用中心扩展法。4. 马拉车算法真正的O(n)解法4.1 预处理填充分隔符解决奇偶问题马拉车算法Manachers Algorithm是这个问题的终极解法时间复杂度是O(n)。我第一次看到这个算法的时候觉得它很玄乎但其实拆开来看核心就是两件事预处理字符串利用对称性减少重复计算。先看预处理。前面提到回文分为奇数和偶数两种长度处理起来很麻烦。马拉车算法巧妙地在每个字符之间插入一个特殊分隔符比如#并在开头结尾也加上让所有回文都变成奇数长度。举个例子原始字符串abba经过处理后变成#a#b#b#a#原来的偶数长度回文abba变成了奇数长度的#a#b#b#a#中心是中间的#。原始字符串aba处理后变成#a#b#a#中心是b。这样一来所有的回文中心都统一成了一个字符不用再区分奇数还是偶数。注意分隔符的选择不能是原字符串中可能出现的字符通常用#也可以根据题目限制用一个不会出现的字符。4.2 利用回文对称性减少计算预处理完之后核心就变成了计算一个数组p[i]表示以第i个字符为中心的最长回文半径包含中心本身。比如p[i] 3表示以i为中心的回文串向左右各扩展了2个字符。经过推导以原始字符串中的字符为中心时p[i] - 1就是原始字符串中该中心对应的回文长度。马拉车算法的关键在于维护两个变量center当前能延伸到最右端的回文中心和right该回文的最右边界。当遍历到i时如果i right那么可以利用对称性找到i关于center的镜像位置mirror 2 * center - i则至少可以确定p[i]不会小于min(right - i, p[mirror])。换句话说不需要再从长度1开始重新扩展而是可以直接从一个已知的下界开始这就省去了大量重复计算。这一点非常巧妙。它的原理是因为center为中心的回文串覆盖了[left, right]区间在这个区间内左右两侧是对称的所以i的回文半径至少和镜像点的回文半径相同除非镜像点的回文范围超出了center回文的左边界此时只能用right - i作为下界。实现了这个下界之后再继续向两边扩展验证最后更新center和right。由于right在算法运行过程中单调递增每个位置最多被扩展一次因此总时间复杂度是O(n)。马拉车的完整实现如下def longestPalindrome(s): if not s: return T #.join(^{}$.format(s)) n len(T) p [0] * n center, right 0, 0 for i in range(1, n - 1): if i right: mirror 2 * center - i p[i] min(right - i, p[mirror]) while T[i p[i] 1] T[i - p[i] - 1]: p[i] 1 if i p[i] right: center, right i, i p[i] max_len, center_idx max((p[i], i) for i in range(1, n - 1)) start (center_idx - max_len) // 2 return s[start:start max_len - 1]这里用^{和$作为哨兵字符避免边界判断。另外注意最终最长回文长度是max_len - 1起始位置是(center_idx - max_len) // 2这两个公式都是经过推导的直接代入即可。马拉车算法的代码虽然短但每一步都值得仔细琢磨。尤其是while循环里的边界条件很容易因为哨兵字符设置不当而越界。我建议初学者先理解预处理的作用再动手实现不要直接背代码。5. 常见Bug与面试实战经验5.1 边界条件与细节陷阱刷题过程中我总结了一些特别容易出问题的地方空串和单字符longestPalindrome()应该返回longestPalindrome(a)应该返回a。很多实现会在n 2时直接返回s这是安全的但要注意有些写法在n 1时会初始化max_len 1逻辑上没错但容易让人忽略单字符本身是回文这个前提。重复字符串比如aaaa所有子串都是回文最长的是整个串。中心扩展法对这种用例表现很好每次扩展都能走到边界。马拉车在这种用例下也能体现出O(n)的优势因为对称性让大部分位置的半径直接通过镜像确定不会做额外的比较。返回子串的区间很多错误不在于算不出最大长度而在于返回的区间算错了。动态规划里用start和max_len记录结果最后要记得是s[start:startmax_len]不是s[start:startmax_len1]。中心扩展法的返回值是左右边界闭区间马拉车的起始下标公式也需要反复验证。Python切片语义Python中s[i:j]是左闭右开区间拿到子串的时候容易差一个字符。我一般会先在草稿纸上画出下标再写代码能减少这类低级错误。还有一个我觉得特别值得说的观察这道题在LeetCode上数据范围是1 s.length 1000所以O(n²)的解法完全够用。但很多面试官会追加问题如果字符串长度是10万怎么办这时候就必须考虑马拉车算法。也就是说面试中至少要掌握中心扩展法和动态规划马拉车可以作为加分项展示。5.2 面试官到底想考察什么这道题在面试中的定位很有意思。它看起来是“找最优子结构”的字符串问题但实际上考察了三层能力第一层是分析和拆解能力。暴力解法谁都能想到但能不能意识到回文分奇偶长度、中心有2n-1个这是对问题本质的观察。很多面试者卡在不知道如何统一处理奇偶长度这就是对问题模型理解不够。第二层是动态规划的基本功。能不能写出状态转移方程能不能理解遍历顺序对二维表填充的影响这些都可以直接映射到其他DP题目上。例如dp[i][j]的“由短推长”思路和编辑距离、最长公共子串是相通的。而且这道题的状态定义是布尔型比数值型的DP更抽象更能看出一个人是不是真的理解了DP的本质。第三层是知识深度。马拉车算法不是一个能现场推出来的算法需要提前学习和练习。面试时如果能在写完中心扩展之后主动提到“还可以用Manacher优化到O(n)”并且在面试官的追问下把原理讲清楚会是很强的加分项。但要注意如果马拉车理解不透彻讲起来漏洞百出反而会给面试官留下“背模板”的印象不如踏踏实实把中心扩展讲清楚。我自己的经验是在面试中用中心扩展法作为主要解法花30秒时间简单提一下“这道题还有O(n)的马拉车算法一般工程场景下O(n²)已经够用”然后重点讲清楚中心扩展为什么是O(n²)以及和暴力解相比优化在哪里。这样的回答节奏既不显得卖弄也能展示出思维的深度。最后再分享一个小技巧刷这道题的时候可以顺便把“回文子串的个数”LeetCode 647也做掉。那道题几乎是这道题的变体中心扩展法几乎可以直接复用只需要把每次扩展到的回文串计数即可。把这两道题放在一起练习对回文问题的理解会扎实很多。我自己刷完这两道题之后再看字符串类的DP问题状态定义和遍历顺序的敏感度明显提高了。