Временная сложность этого "кратчайшего палиндрома" рекурсивного решения Python - PullRequest
0 голосов
/ 09 ноября 2018

Вот вопрос и код:

Если задана строка s, вы можете преобразовать ее в палиндром, добавив перед ней символы.Найдите и верните самый короткий палиндром, который вы можете найти, выполнив это преобразование.

Пример 1:

Входные данные: "aacecaaa" Выходные данные: "aaacecaaa" Пример 2:

Входные данные:«abcd» Вывод: «dcbabcd»

Рекурсивное решение этой проблемы:

def solution(s):
    i = 0
    for j in range(len(s) - 1, -1, -1):
        if s[i] == s[j]:
            i += 1
    if i == len(s):
        return s
    return s[i:][::-1] + self.shortestPalindrome(s[:i]) + s[i:]

Я пытался выяснить временную сложность этого решения в среднем.Я очень ценю вашу помощь!

...