SWIFT: Validar Palíndromo2

     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:

#!/usr/bin/swift


func esPalindromo2(palabra: String) -> Bool { # Complejidad Tiempo O(n) | Espacio O(1)

    var pIzquierda = 0

    var pDerecha = palabra.count - 1

    var izquierda = palabra.index(palabra.startIndex, offsetBy: pIzquierda)

    var derecha = palabra.index(palabra.startIndex, offsetBy: pDerecha)

    while izquierda < derecha {

        if palabra[izquierda].lowercased() != palabra[derecha].lowercased() { # Comparación

            return false;

        }

        pIzquierda = pIzquierda + 1

        pDerecha = pDerecha - 1

        izquierda = palabra.index(palabra.startIndex, offsetBy: pIzquierda)

        derecha = palabra.index(palabra.startIndex, offsetBy: pDerecha)

    }

    return true

}


print(esPalindromo2(palabra: "mex"))

print(esPalindromo2(palabra: "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