Palíndromo tras una eliminación
La misión
Problema
Un juego de palabras acepta un string (cadena) si se lee igual de izquierda a derecha que de derecha a izquierda, y perdona un solo error al escribir. Dado un string s de letras minúsculas, devuelve True si s ya es un palíndromo o se convierte en uno al eliminar exactamente un carácter, y False en caso contrario. El string vacío cuenta como palíndromo.
Ejemplos
Input: s = "racexcar"
Output: True
Por qué: eliminar la x deja "racecar"
Input: s = "abcda"
Output: False
Por qué: tras emparejar las a de los extremos, b y d no coinciden, y quitar cualquiera de las dos sigue fallando
Input: s = ""
Output: True
Por qué: caso límite: no hay nada que comparar, así que no hace falta eliminar nada
Pistas
0 / 3
Probar cada eliminación posible y comprobar cada resultado es cuadrático. La mayor parte del string nunca necesita una segunda mirada.
Mueve dos punteros hacia adentro desde ambos extremos. Mientras los caracteres coincidan, no hay que decidir nada. El único momento interesante es el primer desajuste.
En el primer desajuste, el carácter eliminado tiene que ser uno de los dos que están bajo los punteros. Comprueba si el tramo interior sin el de la izquierda, o sin el de la derecha, es un palíndromo por sí solo. Si los punteros se encuentran sin ningún desajuste, la respuesta ya es sí.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- s holds lowercase letters
- the empty string counts as a palindrome
Solución
Los caracteres externos que coinciden nunca pueden ser el problema, así que los dos punteros (two pointers) los saltan sin gastar la única eliminación. En el primer desajuste, cualquier corrección tiene que eliminar uno de esos dos caracteres, ya que cada carácter fuera de ellos ya tiene su pareja. Eso deja exactamente dos substrings (subcadenas) candidatos, cada uno comprobado con un recorrido simple de palíndromo, y dentro de ellos no aparecen más decisiones. El tiempo es O(n) porque cada carácter se compara como máximo unas pocas veces, y el espacio es O(1).
def almost_palindrome(s):
def is_pal(i, j): # plain two-pointer check of s[i..j]
while i < j:
if s[i] != s[j]:
return False
i, j = i + 1, j - 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
# the one deletion must remove s[i] or s[j]
return is_pal(i + 1, j) or is_pal(i, j - 1)
i, j = i + 1, j - 1
return True
print(almost_palindrome("racexcar")) # -> True
print(almost_palindrome("abcda")) # -> False
print(almost_palindrome("")) # -> True¿Lo que te frena es la idea y no el código? Valid Palindrome lo explica.