LeetCode 最长回文子序列问题中的“Time Limit Exceeded”

Question

我正在尝试在 LeetCode上解决这个问题，内容如下：

遵循最受好评的 Java 解决方案，我想出了以下记忆化的解决方案：

import functools

class Solution:

    def longestPalindromeSubseq(self, s):

        return longest_palindromic_subsequence(s)

@functools.lru_cache(maxsize=None)

def longest_palindromic_subsequence(s):

    if not s:

        return 0

    if len(s) == 1:

        return 1

    if s[0] == s[-1]:

        return 2 + longest_palindromic_subsequence(s[1:-1])

    return max(

        longest_palindromic_subsequence(s[0:-1]),

        longest_palindromic_subsequence(s[1:]))

问题是输入字符串似乎有许多重复字符超出了时间限制：

正如我从引用的讨论中了解到的，如果没有functools.lru_cache，该算法的时间复杂度为 O(2^N)，因为在字符串长度每减少一个字符时，会进行两次递归调用。

但是，讨论指出记忆化的解决方案是 O(N^2)，不应超过时间限制。然而，我并没有真正看到记忆如何降低时间复杂度，而且这里似乎并非如此。

更让我困惑的是，如果解决方案由许多重复的字符组成，它实际上应该在 O(N) 时间内运行，因为每次第一个和最后一个字符相同时，只进行一次递归调用。

有人可以向我解释为什么这个测试失败了吗？

Answer 1

Python 中的字符串切片是O(n)（切片n的长度），而 java 的子字符串是O(1)因为它只是在相同的底层char[]. 但是，您可以通过简单地对具有两个移动索引的同一个字符串进行操作来从等式中删除切片。此外，当 first 和 last 不相同时，您可以将索引移过相同字母的块：@functools.lru_cache(maxsize=None)def longest_palindromic_subsequence(s, start=None, end=None):&nbsp; &nbsp; if start is None:&nbsp; &nbsp; &nbsp; &nbsp; start = 0&nbsp; &nbsp; if end is None:&nbsp; &nbsp; &nbsp; &nbsp; end = len(s) - 1&nbsp; &nbsp; if end < start:&nbsp; &nbsp; &nbsp; &nbsp; return 0&nbsp; &nbsp; if end == start:&nbsp; &nbsp; &nbsp; &nbsp; return 1&nbsp; &nbsp; if s[start] == s[end]:&nbsp; &nbsp; &nbsp; &nbsp; return 2 + longest_palindromic_subsequence(s, start+1, end-1)&nbsp; &nbsp; # you can move indexes until you meet a different letter!&nbsp; &nbsp; start_ = start&nbsp; &nbsp; end_ = end&nbsp; &nbsp; while s[start_] == s[start]:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; start_ += 1&nbsp; &nbsp; while s[end_] == s[end]:&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; end_ -= 1&nbsp; &nbsp; return max(&nbsp; &nbsp; &nbsp; &nbsp; longest_palindromic_subsequence(s, start, end_),&nbsp; &nbsp; &nbsp; &nbsp; longest_palindromic_subsequence(s, start_, end))Memoizaton 应该有很大帮助。输入"abcde"。在这return max(...)部分中，最终将对 进行两次递归调用"bcd"，甚至对进一步嵌入的子串进行更多调用。