LeetCode最长回文子串解法Memory Limit Exceeded问题排查求助

问题背景 #

近期刷了多道LeetCode题，之前解题失败都能明确原因，但这次第5题**Longest Palindromic Substring（最长回文子串）**碰到了棘手问题：

题目要求 #

给定字符串s，返回s中最长的回文子串。

示例1

输入: s = "babad"
输出: "bab"
说明: "aba" 也是有效答案。

示例2

输入: s = "cbbd"
输出: "bb"

我的实现代码 #

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def is_palindrom(word):
            for i,letter in enumerate(word):
                if letter != word[-i-1]:
                    return False
            return True
        out = ""
        checked_words = set()
        def dp(word):
            nonlocal out
            if len(word)>len(out) and word not in checked_words:
                checked_words.add(word)
                if is_palindrom(word) and len(word)>len(out):
                    out = word
                dp(word[:-1])
                dp(word[1:])
        dp(s)
        return out

遇到的问题 #

当输入如下超长字符串时，LeetCode返回Memory Limit Exceeded（内存超限）：

"rgczcpratwyqxaszbuwwcadruayhasynuxnakpmsyhxzlnxmdtsqqlmwnbxvmgvllafrpmlfuqpbhjddmhmbcgmlyeypkfpreddyencsdmgxysctpubvgeedhurvizgqxclhpfrvxggrowaynrtuwvvvwnqlowdihtrdzjffrgoeqivnprdnpvfjuhycpfydjcpfcnkpyujljiesmuxhtizzvwhvpqylvcirwqsmpptyhcqybstsfgjadicwzycswwmpluvzqdvnhkcofptqrzgjqtbvbdxylrylinspncrkxclykccbwridpqckstxdjawvziucrswpsfmisqiozworibeycuarcidbljslwbalcemgymnsxfziattdylrulwrybzztoxhevsdnvvljfzzrgcmagshucoalfiuapgzpqgjjgqsmcvtdsvehewrvtkeqwgmatqdpwlayjcxcavjmgpdyklrjcqvxjqbjucfubgmgpkfdxznkhcejscymuildfnuxwmuklntnyycdcscioimenaeohgpbcpogyifcsatfxeslstkjclauqmywacizyapxlgtcchlxkvygzeucwalhvhbwkvbceqajstxzzppcxoanhyfkgwaelsfdeeviqogjpresnoacegfeejyychabkhszcokdxpaqrprwfdahjqkfptwpeykgumyemgkccynxuvbdpjlrbgqtcqulxodurugofuwzudnhgxdrbbxtrvdnlodyhsifvyspejenpdckevzqrexplpcqtwtxlimfrsjumiygqeemhihcxyngsemcolrnlyhqlbqbcestadoxtrdvcgucntjnfavylip"

本地测试时，解法内存占用约128MB，其中checked_words集合仅占16MB，未出现内存问题。想知道：

1. 导致LeetCode上内存超限的原因是什么？
2. 如何排查程序中占用内存的部分？

问题分析与解答 #

内存超限的核心原因 #

你的解法本质是递归暴力枚举所有可能的子串，问题出在以下几点：

• 大量子串副本+递归栈开销：每次递归调用dp(word[:-1])和dp(word[1:])都会生成新的字符串副本，对于长度为n的输入，子串总数是O(n²)级别。LeetCode的沙盒环境内存限制比本地严格，且会统计所有内存占用——包括递归栈中的临时字符串、调用帧上下文，而本地可能有更宽松的垃圾回收策略，未触发内存阈值。
• checked_words实际内存被低估：本地统计的16MB只是集合本身的开销，集合中存储的每个子串都是独立的Python字符串对象，每个对象除了字符内容，还有对象头、长度字段等额外开销。对于超长输入，checked_words最终会存储O(n²)个不同子串，实际内存占用远超估计。
• 递归深度与调用次数累积：Python递归栈会保存每个调用的上下文，当输入字符串很长时，递归深度和调用次数指数级增长，栈内存消耗会成为不可忽视的部分。

内存排查方法 #

• 跟踪临时对象与递归开销：
  • 使用sys.getsizeof()统计每个生成子串的内存，在dp函数中加入print(sys.getsizeof(word))，观察每次递归的子串内存占用；
  • 用tracemalloc模块监控内存分配：开头加入import tracemalloc; tracemalloc.start()，结束时打印tracemalloc.get_traced_memory()，查看峰值内存和内存分配最多的对象类型。
• 统计checked_words真实占用：
  • 计算集合中所有字符串的总内存：sum(sys.getsizeof(s) for s in checked_words)，这才是集合存储内容的实际开销，而非集合本身的大小。
• 对比环境差异：
  • LeetCode的Python版本可能与本地不同，不同版本的字符串内存布局、垃圾回收机制有差异，比如旧版本字符串内存占用更高，或垃圾回收触发时机更晚。
• 替换递归为迭代：
  • 把递归逻辑改成迭代，用下标表示子串的起始和结束位置（而非生成新字符串），避免递归栈的内存消耗，直观观察内存变化。

额外优化建议 #

你的解法时间复杂度是O(n³)（枚举O(n²)个子串，每个子串判断回文O(n)），对于超长输入不仅内存超限，时间也会超时。建议改用中心扩展法（时间O(n²)，空间O(1)）或Manacher算法（时间O(n)，空间O(n)），大幅降低内存和时间消耗。

内容的提问来源于stack exchange，提问作者Anytokin