Определение того, является ли строка k-палиндромом, не только удалением первого и последнего символов
Я как раз писал программу для определения, является ли заданная строка палиндромом, когда из нее удалено не более n букв. Я придумал программу на питоне, которая работает, но только путем рекурсивного удаления первых или последних символов строки. Он не удаляет/не проверяет, что происходит, когда вы удаляете символы, которые не находятся на одном из концов. Мне было интересно, как я могу улучшить свою программу, чтобы она проверяла все возможности. Это мой код до сих пор:
def palindromecheck(s,n):
#print(s)
#print(n)
if (len(s)) <=1:
return True
if n==0:
return False
while s[0] == s[(len(s)-1)]:
s=s[1:-1]
if len(s) <= 1:
return True
return palindromecheck((s[:-1]),(n-1)) or palindromecheck((s[1:]),(n-1))
Ответы 1
Это типичная проблема DP. Вы можете попробовать использовать DP (вспомогательная функция memo() для сохранения повторений). Идея состоит в том, чтобы найти самую длинную палиндромную подпоследовательность данной строки. Затем |lps - исходная строка| <= к, сделать вывод, что строка является k-палиндромом.
def checkPalindrome(s: str, k: int) -> bool:
# memo to save the repeatition
memo = {}
def helper(start, end):
if start >= end: return 0 # <= 1 char is a palindrome
if (start, end) in memo:
return memo[(start, end)]
if s[start] == s[end]:
result = helper(start + 1, end - 1)
else:
result = 1 + min(helper(start + 1, end), \
helper(start, end - 1))
memo[(start, end)] = result
return result
return helper(0, len(s) - 1) <= k
В качестве альтернативы вы можете использовать lru_chache для получения промежуточных результатов:
from functools import lru_cache
from typing import List
def checkPalindrome(w: str, k: int) -> bool:
@lru_cache(maxsize=None)
def helper(s, e):
if s > e: return 0
if w[s] != w[e]:
return 1 + min(helper(s+1, e), \
helper(s, e-1))
else:
return helper(s+1, e-1)
return helper(0, len(w)-1) <= k
w = "asparagus"
k = 4
print(checkPalindrome(w, k))
Большое спасибо! Мне просто интересно, можете ли вы прокомментировать код, чтобы объяснить, что он делает. Я как бы изо всех сил пытаюсь понять это, так как я не делал DP раньше.
Код очень простой, если вы сможете запустить его на нескольких примерах на pythontutor.com — вы получите больше понимания. (вот как мы учимся в начале). Рад, что вы можете это полезно. Если это приемлемо, не могли бы вы тогда проголосовать?
что делает '\' в этой ситуации?
это способ Python сказать, что строка продолжается до следующей строки (без разрыва). В противном случае его трудно читать и более 80 символов в одной строке. Вы могли бы PEP (забыл номер).
аааа вижу. Также как именно min() возвращает минимум двух вызываемых функций?
также что именно содержит переменная результата? что показывает результат?
Хотите запустить программу и узнать в инструменте - pythontutor.com?
Я использовал наставника Python для запуска кода. Немного помогло, но я все еще в замешательстве
Программа мне кажется хорошей. Только условие
n==0должно быть лучшеn<0. Каковы примеры случаев, когда это не удается?