Palíndromo ignorando la puntuación
La misión
Problema
Decide si un string (cadena) se lee igual de izquierda a derecha que de derecha a izquierda una vez que ignoras las mayúsculas y minúsculas y saltas todo carácter que no sea una letra o un dígito. Escríbelo primero como una función recursiva que compara los dos extremos y hace la llamada recursiva sobre lo que queda entre ellos, y luego conviértelo en un bucle que maneje strings de cualquier longitud.
Ejemplos
Input: s = "A man, a plan, a canal: Panama"
Output: True
Por qué: solo las letras se leen amanaplanacanalpanama en ambos sentidos
Input: s = "race a car"
Output: False
Por qué: raceacar invertido es racaecar
Input: s = ".,!"
Output: True
Por qué: caso límite: no queda nada después de saltar la puntuación, y un string vacío es un palíndromo
Pistas
0 / 3
Mira el par de caracteres más externo. Si alguno es puntuación, descártalo y vuelve a hacer la misma pregunta. Si ambos cuentan y son distintos, la respuesta es no.
Pasa dos índices, i desde la izquierda y j desde la derecha, en lugar de hacer slices, para que cada llamada sea O(1). El caso base es i >= j.
Cada llamada recursiva es lo último que hace la función, y su resultado se devuelve sin cambios, así que es una llamada de cola. Python conserva todos los frames de todos modos, así que reescríbela como un bucle while que actualice i y j donde antes estaban las llamadas.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Solución
La versión recursiva expresa la definición directamente: salta un extremo que no sea alfanumérico, falla ante un par que no coincide y, si no, mueve ambos extremos hacia adentro. Cada llamada recursiva está en posición de cola, ya que su resultado se devuelve sin cambios y no queda trabajo después, así que el stack frame (marco de pila) que hizo la llamada es peso muerto. Python no reutiliza esos frames, así que un string de unos pocos miles de caracteres supera el límite de recursión aunque la lógica esté bien. El bucle es la traducción mecánica: los parámetros i y j pasan a ser variables, y cada llamada de cola se convierte en una actualización de ellos seguida de otra vuelta por el bucle. Ambas versiones corren en O(n) de tiempo; la recursiva usa O(n) de pila y el bucle, O(1).
def is_palindrome(s, i=0, j=None):
if j is None:
j = len(s) - 1
if i >= j:
return True
if not s[i].isalnum():
return is_palindrome(s, i + 1, j)
if not s[j].isalnum():
return is_palindrome(s, i, j - 1)
if s[i].lower() != s[j].lower():
return False
return is_palindrome(s, i + 1, j - 1) # tail call: nothing happens after it
def is_palindrome_loop(s):
i, j = 0, len(s) - 1
while i < j: # each tail call becomes one update
if not s[i].isalnum():
i += 1
elif not s[j].isalnum():
j -= 1
elif s[i].lower() != s[j].lower():
return False
else:
i, j = i + 1, j - 1
return True
print(is_palindrome("A man, a plan, a canal: Panama")) # -> True
print(is_palindrome("race a car")) # -> False
print(is_palindrome(".,!")) # -> True
print(is_palindrome_loop("ab" * 50000 + "a")) # -> True¿Lo que te frena es la idea y no el código? Llamadas de cola y bucles lo explica.