Valid Palindrome

Last updated May 26, 2024 Edit Source

# Resumen

Inicializa dos punteros, uno a la izquierda del string otro a la derecha del string. Cada uno se movera en direcciones opuestas, el inicializado a la izquierda ira hacia la derecha (++) y el de la derecha hacia la izquierda (–).
Itera hasta que el puntero de la izquierda sea menor o igual que el de la derecha
Compara los caracteres en ambos punteros,
- Si son diferentes, retorna false, no es un palindromo
- Si son iguales, reduce los dos punteros para seguir iterando
Si saliste del ciclo y no hubo ningun caracter diferente, retorna true, es un palindromo

# Problema

El enunciado del problema basicamente busca comparar dos strings, y ver si estos son un palindromo. Un palindromo es una palabra que se lee igual de izquierda a derecha y viceversa.

La forma mas simple del problema son palabras sencillas como “abcba”, sin embargo hay variaciones que incluyen simbolos y los tienes que remover, que incluyen espacios y los tienes que remover, entre otros.

Algunos ejemplos:

race a car no es un palindromo debido a que:

r a c e a c a r
r a c a e c a r No se lee igual de izquierda a derecha

A man, a plan, a canal: Panama es un palindromo debido a que:

a m a n a p l a n a c a n a l p a n a m a
a m a n a p l a n a c a n a l p a n a m a Se lee igual de izquierda a derecha, ignorando todos los caracteres que no son letras o numeros.

Dado un String s la funcion retornara true o false dependiendo de si este es un palindromo o no.

# Parte 1. Caracteres permitidos

Para resolver este problema, primero necesitamos una forma de deshacernos de los caracteres que no sean alfanumericos o de ignorarlos en caso de encontrar uno. Aqui veremos las dos alternativas que tenemos.

# Remover caracteres con un Regex

Para esto, podemos utilizar un simple regex y hacer replace de los caracteres que no se encuentren en el. Un regex valido podria ser: [^a-zA-Z0-9]*

[ - Se abre un grupo de caracteres
^ - Selecciona cualquier caracter que no se encuentre descrito en el siguiente grupo
a-z - Simblos de la a - z (minuscula)
A-Z - Simbolos de la A - Z (mayuscula)
0-9 - Numeros
] - Se cierra el grupo
* - 0 o Mas veces aplica esta regla (Para todo el string)

Acompañado de una funcion como replaceAll, podemos remover todos los caracteres.

# Ignorar los caracteres

Otra forma de hacerlo, es al momento de checar si es un palindromo o no, simplemente saltar los caracteres que no sean un numero o una letra. Para esto podemos utilizar funciones de libreria estandar como Character.isLetterOrDigit o manteniendo un array con los caracteres permitidos, o incluso utilizando matematicas combinado con el codigo ASCII que algunos lenguajes todavia usan para sus caracteres.

# Two Pointers | Checando si es un palindromo

Una vez se eligio la estrategia para lidiar con los caracteres, se puede proceder a realizar la comprobacion, esto puede ser facilmente realizado utilizando la tecnica de notes/Two Pointers. La cual nos indica que podemos inicializar dos punteros para mantener estado en la funcion.

Estos dos punteros iran de forma inversa, uno ira desde 0 hasta str.length y el otro desde str.length hacia 0.

# Codigo

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public boolean isPalindrome(String s) {
        char[] copyArr = s.replaceAll("[^0-9A-Za-z]*", "")
				          .toLowerCase()
				          .toCharArray();

        for (int i = 0, j = copyArr.length -1; i < copyArr.length && j >= 0; i++, j--) {
            if (copyArr[i] != copyArr[j]) {
                return false;
            }
        }
        
        return true;
    }
}

Una implementacion mas tradicional y actualizada de la tecnica de los dos punteros, es utilizando un ciclo while

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Main {
	public boolean isPalindrome(String s) {
		int left = 0;
		int right = s.length() - 1;

		while (left <= right) {
			char leftChar = s.charAt(left);
			char rightChar = s.charAt(right);

			if (leftChar != rightChar) {
				return false
			}

			left++;
			right--;
		}

		return true;
	}
}

# Time Complexity

O(n)

# Space Complexity

O(1)

# Reverse String | Checando si es un palindromo

Una solucion alternativa que es un poco menos eficiente (debido a que utilizas mas espacio) es revertir el string, guardarlo en una variable y hacer la comparacion para saber si es un palindromo. Para esto, se pueden utilizar ciclos, sin embargo, no es tan eficiente como utilizar Two Pointers.

# Referencias

https://www.educative.io/courses/grokking-coding-interview-patterns-java/solution-valid-palindrome

🌱 Digital Garden