LeetCode最长回文子序列问题的“超过时限”
LeetCode最长回文子序列问题的“超过时限”
提问于 2018-09-27 06:55:54
我正在试图解决这个问题 on 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)时间内运行，因为每次第一个字符和最后一个字符相同时，只进行一个递归调用。
有人能解释一下为什么这个考试不及格吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-09-27 07:11:25
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))回忆录应该会有很大帮助。接受输入"abcde"。在return max(...)部分中，最终将对"bcd"进行两个递归调用，并对进一步嵌入的子字符串进行更多的调用。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52531165
复制相关文章
相似问题
腾讯云开发者
