Comments 11
В данном случае динамическое программирование совершенно избыточно.
Достаточно посчитать количество вхождений букв, затем взять одну из букв с меньшей частотой, она будет центром палиндрома. А теми буквами, количество вхождений которых больше одного, "нарастить" палиндром.
Рассмотрим ваш пример "коловорот". В нём 4 буквы "о" и остальные встречаются по одному разу. Берём одну из них, пусть это будет "к", и окружаем его "о", получится "оокоо".
Или "aabbbbccddd". Тут минимальное вхождение у "a", их две, поэтому они образуют центр "аа". Дальше окружаем слева и справа буквами "b": "bbaabb", затем буквами "c": "cbbaabbc", затем "d" (последнюю, нечётную, выкидываем): "dcbbaabbcd".
Итого два прохода: первый по исходной последовательности, второй — по частотам.
Несколько комментариев:
В персчете динамики не нужно рассматривать 3 случая, достаточно только двух. Вариант (i+1, j-1) избыточен, ведь любой палиндром в этой подстроке обязательно лежит в подстроках (i, j-1) и (i+1, j). Это мелкая оптимизация и сильно она не влияет на скорость работы, но все же бросается в глаза.
Временную сложность рекурсивной динамики можно оценить также просто, как и итеративной версии: тупо перемножаете количество состояний (возможных вариантов параметров) на сложность вычисления одного состояния. У вас O(n^2) состояний, каждое считается за константу.
Это найдет оценку сверху, ведь рекурсивная реализация не во всех задачах обходит все состояния. Поэтому рекурсивную реализацию иногда еще называют ленивой. Но в этой задаче обойдутся все состояния.
По коду, вместо
for k in range(1, n + 1): for i in range(n - k + 1): j = i + k - 1
можно сделать:
for i in range(n): for j in range(i, n):
def f(s: str) -> str:
prev, cur = [''] * len(s), s
for gap in range(1, len(s)):
cur, prev = [f'{ch}{prev[i]}{ch}' if s[i] == ch
else max(cur[i:i + 2], key=len)
for i, ch in enumerate(s[gap:])], cur[1:-1]
return (cur[0] if s else '')
На самом деле, у вас сейчас n^2, а у автора вообще n^3. Но меньше квадрата тут никак. Только если вам нужна только длина, а не сами палиндромы (тогда можно хранить только длины в динамике). Если же вам нужны палиндромы, то хранить длины не поможет — придется хранить всю матрицу для восстановления ответа.
хранить в ячейках dp кортежи (длина палиндрома, индекс первого символа палиндрома, индекс последнего). Получим в итоге кортеж про длиннейший палиндром — тогда крайний символ кладём на стек, а у строки обрубаем начало и конец, включая эти первый и последний символы; если её длина <= 1 — палиндром считай восстановлен, иначе — опять ищем max на обкорнаной строке.
Извращение, конечно.
from operator import itemgetter
def f(s: str) -> str:
def helper(s):
prev = [(0, i, i) for i in range(len(s))]
cur = [(1, i, i) for i in range(len(s))]
key = itemgetter(0)
for gap in range(1, len(s)):
cur, prev = [(prev[i][0] + 2, i, i + gap) if s[i] == ch
else max(cur[i:i + 2], key=key)
for i, ch in enumerate(s[gap:])], cur[1:-1]
return cur[0]
st = []
while len(s) > 1:
le, lo, hi = helper(s)
if le < 2:
s = s[lo:lo + le]
else:
st.append(s[lo])
s = s[lo + 1:hi]
return (''.join([*st, s, *st[::-1]]))
print(repr(f('aba')))
Есть замечание про итеративный вариант. Чтобы избежать ловушки off-by-one я бы немного упростил.
for k in range(n):
for i in range(n - k):
j = i + k
Укрощаем динамику в задаче о палиндромах