字符串算法里有个经典问题：给定一串字符，找出其中最长的回文子串。回文就是正读反读都一样的序列，比如"madam"或"racecar"。子串则要求字符连续，"app"是"apple"的子串，"ale"却不是。
这道题的限制条件很清晰：输入只包含数字和英文字母，长度在1到1000之间。输出要求返回最长回文子串本身，如果有多个答案，返回任意一个即可。比如输入"babad"，"bab"和"aba"都是正确答案；输入"cbbd"，则只能返回"bb"。
最直观的暴力解法是枚举所有子串，逐一检查是否为回文。但子串数量是O(N²)，每次检查又要O(N)，总复杂度达到O(N³)，对于长度1000的字符串显然太慢。优化的关键藏在回文的对称性里。
观察发现，任何回文都有一个中心点。奇数长度回文的中心是单个字符，比如"racecar"的'e'；偶数长度回文的中心在两个字符之间，比如"abba"的两个'b'中间。从这个中心向两侧扩展，只要左右字符相等，回文就继续增长。
基于这个洞察，"中心扩展法"应运而生。具体做法是：遍历字符串的每个位置，把它当作奇数长度回文的中心，同时把它和下一个位置当作偶数长度回文的中心，分别向两边扩展。每次扩展记录找到的最长回文，最终答案就是所有记录中的最大值。
实现时需要一个小技巧。写一个辅助函数expand_around_center(s, left, right)，从给定的左右边界开始向外扩展：left左移，right右移，直到越界或字符不等为止。循环终止时，回文长度等于right - left - 1。对奇数情况调用(i, i)，偶数情况调用(i, i+1)，一次遍历就能覆盖所有可能的中心。
时间复杂度降到O(N²)，空间复杂度只有O(1)。对于面试场景，这个解法兼顾了效率和可解释性——不需要动态规划表，也不需要预处理，几行代码就能讲清楚对称扩展的核心思想。
热门跟贴