OPTIMIZADO: Esta segunda versión de la función para validar que una cadena ingresada es palíndromo, es mejor que la anterior, pues maneja el espacio de una forma más eficiente:
function esPalindromo2(palabra) { // Complejidad Tiempo O(n) | Espacio (1)
let izquierdo = 0;
let derecho = palabra.length - 1;
while (izquierdo < derecho) {
if (palabra[izquierdo].toLowerCase() != palabra[derecho].toLowerCase()) // Comparación
return false;
izquierdo++;
derecho--;
}
return true;
}
exports.esPalindromo2 = esPalindromo2;
console.log(esPalindromo2("mex"));
console.log(esPalindromo2("Lol"));
1. Para conseguirlo, en lugar de invertir la cadena ingresada inicialmente, se implementan dos punteros, uno al inicio y otro al final de la cadena.
2. Si el contenido de la cadena al que apuntan ambos punteros es el mismo, se mueven ambos con dirección a la mitad de la cadena.
3. Si en algún punto, los punteros son diferentes, se regresa False. En caso de que nunca sean distintos, podemos determinar que la cadena es un palíndromo, por tanto se regresa True.
4. La complejidad espacial es constante (1), ya que únicamente recorremos la palabra original.
0 remarks:
Publicar un comentario