Вот вопрос и код:
Если задана строка 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:]
Я пытался выяснить временную сложность этого решения в среднем.Я очень ценю вашу помощь!