python - "Time Limit Exceeded"关于 LeetCode 的最长回文子序列问题

Question

我正在尝试解决 this problem在 LeetCode 上，内容如下:

正在关注 the most upvoted Java solution , 我想出了以下 memoized 解决方案:

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[] 上创建一个 View 。但是，您可以通过简单地对具有两个移动索引的相同字符串进行操作来将切片从等式中取出。此外，当第一个和最后一个不相同时，您可以将索引移过相同字母的 block :

@functools.lru_cache(maxsize=None)
def longest_palindromic_subsequence(s, start=None, end=None):
    if start is None:
        start = 0
    if end is None:
        end = len(s) - 1
    if end < start:
        return 0
    if end == start:
        return 1
    if s[start] == s[end]:
        return 2 + longest_palindromic_subsequence(s, start+1, end-1)

    # you can move indexes until you meet a different letter!
    start_ = start
    end_ = end
    while s[start_] == s[start]: 
        start_ += 1
    while s[end_] == s[end]: 
        end_ -= 1

    return max(
        longest_palindromic_subsequence(s, start, end_),
        longest_palindromic_subsequence(s, start_, end))

Memoizaton 应该会有很大帮助。接受输入 "abcde"。在 return max(...) 部分，最终将对 "bcd" 进行两次递归调用，并对进一步嵌入的子字符串进行更多调用。