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

Question

我正在尝试解决 LeetCode 上的 this problem，内容为：

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

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

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

"Time Limit Exceeded" on LeetCode's Longest Palindromic Subsequence question

python

algorithm

memoization

time-complexity