Palindrome String

Q: ¿Cómo compruebas 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 diferente, la cadena no es un palíndromo; si todos los pares coinciden, sí lo es. Dos índices que empiezan en ambos extremos y avanzan hacia el interior lo hacen en una sola pasada.

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

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

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

Es 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 una cadena cuyos caracteres primero y último son distintos se determina tras una comparación.

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

Sí. Una cadena de un carácter se lee igual en ambas direcciones, así que la respuesta es true . En el bucle de dos punteros, left y right empiezan 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 alfabeto 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.

+16 pruebas ocultas al enviar

Para ir más allá

Una oración como Was it a car or a cat I saw es un palíndromo si ignoras las mayúsculas y minúsculas, los espacios y la puntuación. ¿Cómo cambiarías los dos punteros para omitir esos caracteres?

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 la comprobación directa construye el reverso y lo compara. La mejor comprobación no construye nada: el primer carácter debe coincidir con el último, el segundo con el penúltimo, y así sucesivamente hacia el centro. Dos índices que avanzan hacia dentro comprueban esos pares en el lugar y se detienen en la primera discrepancia.

Compara la cadena con su reverso

Intuición

Leer s igual en ambas direcciones significa que s es igual a su reverso. Así que inviértela y compárala: racecar invertida es racecar, y coddy invertida es yddoc, que es diferente.

Construir el reverso y comparar cada uno recorre todos los caracteres una vez, así que el tiempo es O(n). La copia invertida contiene n caracteres más, lo que supone O(n) de espacio adicional: con n = 5 × 10^4, son 50 000 caracteres creados solo para compararlos y descartarlos.

Además, realiza todo el trabajo cada vez. El resultado para coddy se determina por su primera y última letra, pero este enfoque invierte las cinco letras antes de comprobarlo.

Algoritmo

Construye la cadena invertida de s con la función reverse del lenguaje o con un bucle que vaya desde el último carácter hasta el primero.
Compara la cadena invertida 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

Al invertir, el carácter del índice i pasa 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 lista, así que comprueba solo la mitad izquierda. Coloca left en el índice 0 y right en el índice n-1, compara los dos caracteres y mueve ambos punteros un paso hacia el interior.

Detente cuando los punteros se encuentren o se crucen. En racecar comprueban los pares de índices (0, 6), (1, 5) y (2, 4), y luego se encuentran en el índice 3, la e central, que no necesita pareja. En abba comprueban (0, 3) y (1, 2) y luego se cruzan. El primer par que difiere demuestra que la respuesta es false, así que devuelve el resultado de inmediato: coddy se decide tras una comparación.

Se realizan como máximo n / 2 comparaciones, lo que supone un tiempo de O(n), y la única memoria son dos índices, es decir, un espacio de O(1). R es la excepción: 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 coincidirán: 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

El bucle es corto, así que los errores están en sus límites y en sus instrucciones return.

Devolver true en cuanto coincide un par. abca pasa el par exterior y falla en el interior, así que true solo puede devolverse después de que termine el 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 empieza en n.
Comparar cadenas por dirección. En C, reversed == s compara dos punteros y siempre es falso para una copia nueva; usa strcmp.
Construir la cadena invertida con result = result + ch en un bucle. Cada paso copia toda la cadena acumulada hasta ese momento, lo que supone 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 con sus propios índices o copia los caracteres en un arreglo.

Preguntas frecuentes4

¿Cómo compruebas 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 diferente, la cadena no es un palíndromo; si todos los pares coinciden, sí lo es. Dos índices que empiezan en ambos extremos y avanzan hacia el interior lo hacen en una sola pasada.

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

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

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

Es 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 una cadena cuyos caracteres primero y último son distintos se determina tras una comparación.

¿Un solo carácter es un palíndromo?

Sí. Una cadena de un carácter se lee igual en ambas direcciones, así que la respuesta es true. En el bucle de dos punteros, left y right empiezan en el índice 0, el bucle nunca se ejecuta y la función devuelve true.

Python

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

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "racecar"

Esperado

true