Categorías
Algorithms Interview

LeetCode – Palíndromo más corto (Java)

Dada una cadena S, puede convertirla en un palíndromo agregando caracteres delante de ella. Busque y devuelva el palíndromo más corto que pueda encontrar realizando esta transformación.

Por ejemplo, dado «aacecaaa», devuelve «aaacecaaa»; dado «abcd», devuelve «dcbabcd».

Solución Java 1

public String shortestPalindrome(String s) {
    int i=0; 
    int j=s.length()-1;
 
    while(j>=0){
        if(s.charAt(i)==s.charAt(j)){
            i++;
        }
        j--;
    }
 
    if(i==s.length())
        return s;
 
    String suffix = s.substring(i);
    String prefix = new StringBuilder(suffix).reverse().toString();
    String mid = shortestPalindrome(s.substring(0, i));
    return prefix+mid+suffix;
}

Solución Java 2

Podemos resolver este problema utilizando uno de los métodos que se utilizan para resolver el problema de subcadena palíndromo más largo.

Específicamente, podemos comenzar desde el centro y escanear dos lados. Si lee el límite izquierdo, entonces se identifica el palíndromo más corto.

public String shortestPalindrome(String s) {
	if (s == null || s.length() <= 1)
		return s;
 
	String result = null;
 
	int len = s.length();
	int mid = len / 2;	
 
	for (int i = mid; i >= 1; i--) {
		if (s.charAt(i) == s.charAt(i - 1)) {
			if ((result = scanFromCenter(s, i - 1, i)) != null)
				return result;
		} else {
			if ((result = scanFromCenter(s, i - 1, i - 1)) != null)
				return result;
		}
	}
 
	return result;
}
 
private String scanFromCenter(String s, int l, int r) {
	int i = 1;
 
	//scan from center to both sides
	for (; l - i >= 0; i++) {
		if (s.charAt(l - i) != s.charAt(r + i))
			break;
	}
 
	//if not end at the beginning of s, return null 
	if (l - i >= 0)
		return null;
 
	StringBuilder sb = new StringBuilder(s.substring(r + i));
	sb.reverse();
 
	return sb.append(s).toString();
}

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *