Palindrome String

Q: ¿Cómo se comprueba si una cadena es un palíndromo?

Compara el primer carácter con el último, el segundo con el penúltimo, y así sucesivamente hacia el centro. Si algún par es distinto, la cadena no es un palíndromo. Dos índices que empiezan en ambos extremos y avanzan hacia el centro lo hacen en una sola pasada.

Q: ¿Puedes comprobar si una palabra es un palíndromo sin memoria adicional?

Sí. La comprobación con dos punteros lee los caracteres directamente y almacena dos índices, por lo que usa espacio adicional O(1) . Comparar s con su inversa es más breve de escribir, pero crea una segunda cadena de n caracteres.

Q: ¿Cuál es la complejidad temporal de comprobar si una cadena es un palíndromo?

O(n) para una cadena de longitud n . La comprobación con dos punteros realiza como máximo n / 2 comparaciones y se detiene en la primera discrepancia, así que coddy requiere una comparación.

Q: ¿Es un solo carácter un palíndromo?

Sí, se lee igual en ambas direcciones. En el bucle de dos punteros, left y right comienzan ambos en el índice 0, el bucle nunca se ejecuta y la función devuelve true .

PrincipianteDos punteros Arrays y cadenas

+10

Una cadena es un palíndromo cuando se lee igual de izquierda a derecha que de derecha a izquierda, como level. Escribe una función que reciba una cadena s formada por letras minúsculas del inglés y devuelva true si s es un palíndromo y false en caso contrario.

Función

isPalindrome(s: string) → boolean

sstring: la cadena en minúsculas que se debe comprobar
Devuelveboolean: verdadero cuando s se lee igual en ambas direcciones

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo letras minúsculas del inglés (a a z).

Ejemplos

Entrada: s = "racecar"
Salida: true
Explicación: Compara de afuera hacia adentro: r con r, a con a, c con c. La e del medio no tiene pareja ni la necesita, así que la respuesta es true.

Entrada: s = "abba"
Salida: true
Explicación: Con una longitud par, cada letra tiene una pareja: las dos a coinciden y las dos b coinciden, así que la respuesta es true.

Entrada: s = "coddy"
Salida: false
Explicación: La primera letra c y la última letra y ya son diferentes, así que coddy no es un palíndromo y la respuesta es false.

Para ir más allá

¿Cómo cambiarías los dos punteros para que omitan los espacios y la puntuación e ignoren mayúsculas y minúsculas, de modo que Was it a car or a cat I saw se considere un palíndromo?

Pistas

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

0 de 3 abiertas

Solución

Un palíndromo es igual a su reverso, así que puedes construir el reverso y compararlos. No necesitas la copia: el primer carácter debe coincidir con el último, el segundo con el penúltimo, y así sucesivamente. Dos índices que avanzan hacia el interior comprueban esos pares en el lugar y se detienen en la primera discrepancia.

Compara la cadena con su reverso

Intuición

Invierte s y compara: al invertir racecar se obtiene racecar, y al invertir coddy se obtiene yddoc. Una cadena se lee igual en ambos sentidos exactamente cuando es igual a su inversa.

El tiempo es O(n), pero la copia invertida ocupa O(n) de espacio adicional: 50,000 caracteres con n = 5 × 10^4. Además, el trabajo siempre se realiza por completo: el caso de coddy se decide con sus primeras y últimas letras, pero primero se invierten sus cinco letras.

Algoritmo

Construye la inversa de s, con la función de inversión del lenguaje o con un bucle desde el último carácter hasta el primero.
Compara la inversa con s.
Devuelve true si son iguales y false en caso contrario.

def isPalindrome(s):
    return s == s[::-1]

Dos punteros desde ambos extremos

Intuición

Invertir desplaza el índice i al índice n-1-i, así que s es igual a su reverso exactamente cuando s[i] es igual a s[n-1-i] para cada i. Cada par aparece dos veces en esa condición, así que basta con comprobar la mitad izquierda. En racecar, los pares son (0, 6), (1, 5) y (2, 4); la e del medio, en el índice 3, no necesita pareja.

El primer par que difiere demuestra que la respuesta es false, así que el resultado para coddy se determina después de una comparación. Se ejecutan como máximo n / 2 comparaciones: tiempo O(n), y los dos índices requieren espacio O(1). R primero lee la cadena como un vector de códigos de caracteres, lo que cuesta O(n).

Algoritmo

Establece left = 0 y right = n-1.
Mientras left < right, compara s[left] con s[right].
Si son diferentes, devuelve false.
De lo contrario, suma 1 a left, resta 1 a right y repite.
Cuando los punteros se encuentren o se crucen, todos los pares habrán coincidido: devuelve true.

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

Errores comunes y casos límite

Devolver true en cuanto coincida un par. abca supera el par exterior y falla en el interior, así que true solo se devuelve después del bucle.
Iniciar right en n en lugar de n-1, lo que lee más allá del final (en C, el '\0' de terminación). En Lua y R, los índices van de 1 a n, así que allí right sí empieza en n.
Comparar cadenas con == en C. reversed == s compara dos punteros y es falso para una copia; usa strcmp.
Construir la cadena invertida con result = result + ch. Cada paso copia la cadena acumulada: unas 1.25 × 10^9 copias de caracteres para 50,000 letras.
Indexar una cadena de Swift con un entero: no compila. Recorre s.utf8 o copia los caracteres en un arreglo.

Preguntas frecuentes4

¿Cómo se comprueba si una cadena es un palíndromo?

Compara el primer carácter con el último, el segundo con el penúltimo, y así sucesivamente hacia el centro. Si algún par es distinto, la cadena no es un palíndromo. Dos índices que empiezan en ambos extremos y avanzan hacia el centro lo hacen en una sola pasada.

¿Puedes comprobar si una palabra es un palíndromo sin memoria adicional?

Sí. La comprobación con dos punteros lee los caracteres directamente y almacena dos índices, por lo que usa espacio adicional O(1). Comparar s con su inversa es más breve de escribir, pero crea una segunda cadena de n caracteres.

¿Cuál es la complejidad temporal de comprobar si una cadena es un palíndromo?

O(n) para una cadena de longitud n. La comprobación con dos punteros realiza como máximo n / 2 comparaciones y se detiene en la primera discrepancia, así que coddy requiere una comparación.

¿Es un solo carácter un palíndromo?

Sí, se lee igual en ambas direcciones. En el bucle de dos punteros, left y right comienzan ambos en el índice 0, el bucle nunca se ejecuta y la función devuelve true.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

s = "racecar"

Salida Esperada

true