Valid Palindrome

Q: ¿Cuál es la complejidad temporal de Valid Palindrome?

Ambos enfoques se ejecutan en tiempo O(n) , porque cada carácter se examina un número constante de veces. Limpiar primero usa O(n) de memoria adicional para la copia. La versión de dos punteros usa O(1) de memoria adicional, ya que solo conserva dos índices.

Q: ¿Cómo compruebas si una cadena es un palíndromo ignorando los caracteres no alfanuméricos?

Mantén un puntero en cada extremo de la cadena. Avanza un puntero más allá de cualquier carácter que no sea una letra o un dígito y, cuando ambos estén sobre letras o dígitos, compáralos en minúsculas. Si todos los pares comparados coinciden hasta que los punteros se encuentren, la cadena es un palíndromo.

Q: ¿Es una cadena vacía un palíndromo?

Sí. Un texto vacío se lee igual en ambas direcciones, así que una cadena como ?!-_ , cuyos caracteres se ignoran todos, devuelve true . Ambos enfoques lo consiguen sin código adicional: el texto depurado es igual a su reverso vacío, y los dos punteros nunca encuentran un par que difiera.

Q: ¿Por qué usar dos punteros en lugar de invertir la cadena?

Invertir requiere una copia depurada y una copia invertida, lo que supone O(n) de memoria adicional. Dos punteros comparan los mismos pares en el lugar y pueden detenerse en la primera discrepancia, a menudo después de unos pocos pasos. En las entrevistas suelen pedir esta versión como pregunta de seguimiento.

FácilDos punteros

+10

Recibes una cadena s. Conserva solo sus letras y dígitos, trata las mayúsculas y las minúsculas como la misma letra y decide si lo que queda se lee igual de izquierda a derecha que de derecha a izquierda. Devuelve true si es así y false en caso contrario.

Se ignoran todos los demás caracteres, como ., !, ?, :, ;, - o _. Si s no contiene ninguna letra ni dígito, no queda nada, y un texto vacío cuenta como palíndromo.

Función

isPalindrome(s: string) → boolean

sstring: el texto que se va a comprobar, incluida la puntuación
Devuelveboolean: verdadero si las letras y los dígitos de s se leen igual en ambas direcciones, ignorando mayúsculas y minúsculas

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene letras inglesas, dígitos y los signos de puntuación . ! ? : ; - _, sin espacios.

Ejemplos

Entrada: s = "Was_it_a_car_or_a_cat_I_saw?"
Salida: true
Explicación: Quita los guiones bajos y el signo de interrogación y pasa las mayúsculas a minúsculas: obtienes wasitacaroracatisaw, que es igual al revés.

Entrada: s = "race-a-car"
Salida: false
Explicación: Sin los guiones, el texto es raceacar. Si se lee desde la derecha, empieza por raca en lugar de race: la e del medio tiene una a como pareja reflejada, así que la respuesta es false.

Entrada: s = "Step-on-no-pets!"
Salida: true
Explicación: El texto conservado es steponnopets. La S mayúscula coincide con la s final porque se ignoran las mayúsculas y minúsculas, y los guiones y el ! no intervienen.

+25 pruebas ocultas al enviar

Para ir más allá

¿Puedes decidirlo con memoria adicional O(1), sin crear una copia depurada de s?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La comprobación del palíndromo en sí es la habitual: el primer carácter conservado debe ser igual al último, el segundo debe ser igual al penúltimo, y así sucesivamente. Lo que hace complicada esta versión es que los caracteres que comparas no están en índices simétricos de s, porque la puntuación está distribuida de manera desigual a ambos lados. Puedes eliminarla primero o dejar que dos punteros la salten mientras avanzan uno hacia el otro.

Limpia la cadena y después compárala con su inversa

Intuición

Construye el texto por el que realmente pregunta el problema. Recorre s, conserva cada letra o dígito en minúscula y omite todo lo demás. Para Step-on-no-pets!, el resultado es steponnopets. Ahora la pregunta es la típica pregunta sobre palíndromos: ¿este texto es igual a su reverso?

Esto es correcto porque la limpieza elimina exactamente los caracteres que el problema indica que se deben ignorar y convierte a minúsculas los caracteres cuyo uso de mayúsculas y minúsculas se debe ignorar. Si s no contiene letras ni dígitos, el texto limpio está vacío, y un texto vacío es igual a su reverso, así que la respuesta es true sin ningún caso especial.

Cada carácter se lee una vez para limpiarlo y una vez más para compararlo, así que el tiempo es O(n). La copia limpia y su reverso ocupan O(n) de memoria adicional, que es el costo que elimina el siguiente enfoque.

Algoritmo

Crea un texto vacío cleaned.
Para cada carácter de s, si es una letra o un dígito, añádelo en minúsculas.
Invierte cleaned.
Devuelve si cleaned es igual a su inverso.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Dos punteros que omiten la puntuación

Intuición

La copia depurada solo está ahí para que puedas comparar los caracteres reflejados. Puedes hacer la misma comparación directamente en s. Coloca left en el primer índice y right en el último. En cada paso, si left apunta a un signo de puntuación, muévelo a la derecha; si right apunta a un signo de puntuación, muévelo a la izquierda. Cuando ambos apunten a letras o dígitos, compáralos en minúsculas. Si no coinciden, el resultado es false; si coinciden, ambos punteros avanzan hacia el centro.

¿Por qué es esta la misma comprobación? Los punteros siempre se detienen en el siguiente carácter que se conserva desde cada extremo, así que recorren los pares (primer carácter conservado, último carácter conservado), (segundo carácter conservado, penúltimo carácter conservado) y así sucesivamente, que son exactamente los pares que compara la versión invertida. En Abc-dcbX, el primer par es A y X, y el resultado es false después de una comparación.

Cada paso mueve al menos un puntero, y se detienen cuando se encuentran, así que el bucle se ejecuta como máximo n veces. No se almacena nada aparte de los dos índices, lo que requiere O(1) de memoria adicional.

Algoritmo

Establece left = 0 y right = n-1.
Mientras left < right: si s[left] no es una letra ni un dígito, incrementa left y continúa.
De lo contrario, si s[right] no es una letra ni un dígito, decrementa right y continúa.
De lo contrario, compara los dos caracteres en minúsculas. Si son diferentes, devuelve false; si coinciden, mueve ambos punteros hacia el interior.
Cuando los punteros se encuentren, devuelve true.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Errores comunes y casos límite

La mayoría de los errores se deben a los caracteres que se omiten y a las mayúsculas y minúsculas.

Comparar s[i] con s[n-1-i] en la cadena original. a-ba es un palíndromo una vez que se elimina el guion, pero el reflejo de - en el índice 1 en la cadena original es b en el índice 2.
Mover ambos punteros cuando solo uno de ellos está sobre un signo de puntuación. Omite los caracteres de un lado a la vez; de lo contrario, los dos lados se desincronizan.
Omitir los signos de puntuación en un bucle interno que sobrepasa el otro puntero. Con ?!-_, un bucle interno sin límite se sale del final de la cadena; mantén la comprobación left < right en cada movimiento.
Tratar los dígitos como ruido. 0P es false: el dígito 0 se conserva y se compara, y no es la letra p.
Devolver false cuando no se conserva nada. Una cadena que contiene solo signos de puntuación, como ., tiene un texto limpio vacío, que es un palíndromo.
Una cadena compuesta solo por dígitos, como 12321, puede llegar a PHP y R como un número. Primero conviértela en una cadena.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Valid Palindrome?

Ambos enfoques se ejecutan en tiempo O(n), porque cada carácter se examina un número constante de veces. Limpiar primero usa O(n) de memoria adicional para la copia. La versión de dos punteros usa O(1) de memoria adicional, ya que solo conserva dos índices.

¿Cómo compruebas si una cadena es un palíndromo ignorando los caracteres no alfanuméricos?

Mantén un puntero en cada extremo de la cadena. Avanza un puntero más allá de cualquier carácter que no sea una letra o un dígito y, cuando ambos estén sobre letras o dígitos, compáralos en minúsculas. Si todos los pares comparados coinciden hasta que los punteros se encuentren, la cadena es un palíndromo.

¿Es una cadena vacía un palíndromo?

Sí. Un texto vacío se lee igual en ambas direcciones, así que una cadena como ?!-_, cuyos caracteres se ignoran todos, devuelve true. Ambos enfoques lo consiguen sin código adicional: el texto depurado es igual a su reverso vacío, y los dos punteros nunca encuentran un par que difiera.

¿Por qué usar dos punteros en lugar de invertir la cadena?

Invertir requiere una copia depurada y una copia invertida, lo que supone O(n) de memoria adicional. Dos punteros comparan los mismos pares en el lugar y pueden detenerse en la primera discrepancia, a menudo después de unos pocos pasos. En las entrevistas suelen pedir esta versión como pregunta de seguimiento.

Python

def isPalindrome(s):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "Was_it_a_car_or_a_cat_I_saw?"

Esperado

true