«Превышен лимит времени» на вопрос о самой длинной палиндромной подпоследовательности LeetCode

Question

Я пытаюсь решить эту проблему на LeetCode, которая гласит:

После наиболееupvoted решение 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[].Однако вы можете убрать срезы из уравнения, просто оперируя одной и той же строкой с двумя подвижными индексами.Более того, вы можете перемещать индексы за блоки одинаковых букв, когда первое и последнее не совпадают:

@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" и еще больше вызовов для дополнительных встроенных подстрок.