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

Question

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

已关注 the most upvoted Java solution ，我想出了以下内存解决方案:

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"进行两次递归调用，甚至对进一步嵌入的子字符串进行更多调用。