Leetcode内存优化-最长回文子串

Question

最近做了很多 Leetcode 题。当我做某题失败时，我一直都知道为什么，但这次不知道 - 问题 5. 最长回文子串：

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

示例1：

Input: s = "babad"
Output: "bab"

解释：“aba”也是有效答案。

示例2：

Input: s = "cbbd"
Output: "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

问题：输入时超出内存限制：s = “rgczcpratwyqxaszbuwwcadruayhasynuxnakpmsyhxzlnxmdtsqqlmwnbxvmgvllafrpmlfuqpbhjddmhmbcgmlyeypkfpreddyencsdmgxysctpubvgeedhurvizgqxclhpfrvxggrowaynrtuwvvvwnqlowdihtrdzjffrgoeqivnprdnpvf juhycpfydjcpfcnkpyujljiesmuxhtizzvwhvpqylvcirwqsmpptyhcqybstsfgjadicwzycswwmpluvzqdvnhkcofptqrzgjqtbvbdxylrylinspncrkxclykccbwridpqckstxdjawvziucrswpsfmisqiozworibeycuarcidbljslwbalcemgymnsx fziattdylrulwrybzztoxhevsdnvvljfzzrgcmagshucoalfiuapgzpqgjjgqsmcvtdsvehewrvtkeqwgmatqdpwlayjcxcavjmgpdyklrjcqvxjqbjucfubgmgpkfdxznkhcejscymuildfnuxwmuklntnyycdcscioimenaeohgpbcpogy ifcsatfxeslstkjclauqmywacizyapxlgtcchlxkvygzeucwalhvhbwkvbceqajstxzzppcxoanhyfkgwaelsfdeeviqogjpresnoacegfeejyychabkhszcokdxpaqrprwfdahjqkfptwpeykgumyemgkccynxuvbdpjlrbgqtcqulxodurugofuwzudn hgxdrbbxtrvdnlodyhsifvyspejenpdckevzqrexplpcqtwtxlimfrsjumiygqeemhihcxyngsemcolrnlyhqlbqbcestadoxtrdvcgucntjnfavylip“

我已经在本地设置上测试了我的解决方案，并且解决方案不需要大量 RAM 内存 - 大约 128MB（使用 process.memory_info().rss 测试），16MB 仅用于 check_words 集（使用 sys.getsizeof() 测试） ）。 可能有什么问题？如何确定程序的哪一部分导致了内存问题？

Answer 1

Leetcode 对内存使用情况的报告很奇怪。根据该平台，我的解决方案使用 >16MB

虽然确实正在构造新列表（由于切片），但这些列表是暂时的，因此消耗最少的内存 - 即，它们被构造、用于比较，然后（隐式）丢弃。问题描述指出输入字符串将是 <=1000 characters

class Solution:
    def longestPalindrome(self, s: str) -> str:

        def ispalindrome(s):
            return s == s[::-1]
        
        if len(s) < 2:
            return s
        
        start = 0
        size = 1

        for i in range(1, len(s)):
            left = i - size

            if left >= 1 and ispalindrome(s[left-1:i+1]):
                size += 2
                start = left - 1
            else:
                if ispalindrome(s[left:i+1]):
                    size += 1
                    start = left

        return s[start:start+size]

Answer 2

你的代码效率太低；不需要为每个可能的子串运行线性循环来检查它是否是回文。由于此问题的最大字符串长度仅为 1000，因此我们可以使用一个简单的 O(|s|^2) 动态规划解决方案，该解决方案利用了之前的计算结果。

令

is_palindrome[l][r]

表示从索引

l

到

r

（含）的子串是否是回文。首先，我们为所有长度为 1 和 2 的回文初始化该表。 对于长度至少为 3 (

r - l > 2

) 的子串，

is_palindrome[l][r]

将为 true，当且仅当索引

l

和

r

处的字符匹配，并且从两端切除一个字符形成的子串也是回文 (即

is_palindrome[i + 1][r - 1]

为真）。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        is_palindrome = [[False] * len(s) for _ in s]
        ans = s[0]
        for i in range(len(s)): is_palindrome[i][i] = True
        for i in range(len(s) - 1): 
            if s[i] == s[i + 1]:
                is_palindrome[i][i + 1] = True
                ans = s[i:i+2]
        for l in range(3, len(s) + 1):
            for i in range(0, len(s) - l + 1):
                if s[i] == s[i + l - 1] and is_palindrome[i + 1][i + l - 2]:
                    is_palindrome[i][i + l - 1] = True
                    ans = s[i:i+l]
        return ans

请注意，还有一些解决方案可以在 O(|s|) 时间内解决此问题，但这对于此问题来说不是必需的。