Estoy resolviendo los problemas en LeetCode y tocó el turno del palíndromo más largo hayado dentro de una cadena de texto. El problema dice que dada una cadena s, regresar el palíndromo más largo encontrado dentro de s.
Se me ocurrió un enfoque de 2 punteros i, j en el que ambos arrancarían en la posición 0 e iría moviendo j hasta llegar al final de la cadena; en cada paso de j se compararía si la subcadena i:j es igual a la misma subcadena i:j invertida; cuando j llegara al final tanto i como j pasarían a i + 1. Aquí noté que no tendría caso verificar subcadenas de longitud menor al mayor palíndromo encontrado hasta el momento, así que al incrementar i, j sería i más la longitud del mayor palíndromo encontrado. La solución quedó:
class Solution:
def longestPalindrome(self, s: str) -> str:
strLen = len(s)
if len(s) == 1:
return s
i = 0
j = 0
palindrom = ''
# tanto i como j son posiciones válidas
while (i < strLen) and (j < strLen):
# si la substring es un palindromo y la longitud de la
# substring es mayor a la del anterior palindromo encontrado
if s[i:j + 1] == s[i:j + 1][::-1] and (j + 1 - i > len(palindrom)):
palindrom = s[i:j + 1]
j += 1
if (j == strLen):
i += 1
# no me interesan substrings mas cortas que el mayor
# palindromo encontrado hasta ahora
j = i + len(palindrom) - 1
return palindrom
Esta solución tardó 4737ms y solo fue mejor al 12% de las soluciones presentadas en LeetCode. Al analizar mi solución con Claude obtuve el siguiente feedback:
¡Buena optimización lo de saltarjal inicio! La lógica es correcta. Sobre complejidad — tu solución es O(n²) en tiempo porque para cada par(i, j)hacess[i:j+1][::-1]que es O(n). LeetCode lo acepta para este problema. El approach óptimo O(n) es el algoritmo de Manacher, pero es muy complejo para una entrevista. El approach O(n²) de expandir desde el centro es el que esperan normalmente.
Para entender el algoritmo de expandir desde el centro reescribí mi primer solución, pero rápidamente me encontré con un problema: si expando desde el centro entonces solo voy a encontrar palíndromos que tengan su centro en el centro de la cadena original, por lo que consulté otra vez con Claude:
"Expandir desde el centro" significa: Para cada carácter del string, trátalo como el centro de un posible palíndromo y expande hacia afuera. O sea no es el centro del string completo — es que cada posiciónies candidata a ser el centro de su propio palíndromo. Tu solución y este enfoque no difieren mucho en complejidad, ambas son O(n²). La diferencia es:La de expandir es ligeramente más eficiente en práctica porque falla rápido — en cuanto los extremos no coinciden, para. La tuya revisa la substring completa con
- Tu solución: revisa todas las substrings posibles con dos punteros
iyj- Expandir desde el centro: para cada
iexpande hacia afuera mientras sea palíndromo[::-1]aunque no sea palíndromo. Pero conceptualmente son el mismo O(n²).
Cuando finalmente entendí la parte de expandir desde el centro llegué a la siguiente solución:
class Solution:
def longestPalindrome(self, s: str) -> str:
sLen = len(s)
if sLen == 1:
return s
palindrom = s[0]
for i in range(sLen):
even = self.expand(s, i, i + 1)
odd = self.expand(s, i, i)
palindrom = max([palindrom, even, odd], key=len)
return palindrom
def expand(self, s, i, j):
while i > -1 and j < len(s) and s[i] == s[j]:
i -= 1
j += 1
# restaura los últimos valores que cumplieron la condicion
return s[i + 1:j]
A pesar de hacer 2 veces el algoritmo (una para cadenas de longitud par y otra para cadenas de longitud impar), la solución tomó 231ms, siendo mejor que el 82% de las soluciones enviadas. Fue una mejora bastante grande, pero aun faltaba por ver qué hace tan especial a ese algoritmo de Manacher así que volví a consultar con Claude:
Manacher es la versión O(n) y se basa en una observación clave: Si ya encontraste un palíndromo grande, los palíndromos que caen dentro de él ya los conoces — son el espejo de los que están al otro lado del centro. Ejemplo:El palíndromo completo es"cabadabac" índice: 0 1 2 3 4 5 6 7 8 letra: c a b a d a b a c ↑ centro = 'd' en índice 4"cabadabac". Ahora:
- El palíndromo centrado en
bdel índice 2 es"aba"- Su espejo está en el índice 6, también centrado en
b- ¿Necesitas calcular el palíndromo en índice 6? No — ya sabes que también es
"aba"
Y la verdad es que no me quedó para nada claro, así que revisé un poco de literatura en:
Al final con la teoría y los ejemplos de código en las páginas listadas llegué a la siguiente solución:
class Solution:
def longestPalindrome(self, s: str) -> str:
symbol = '#'
sanS = '@' + symbol + symbol.join(s) + symbol + '$'
sanSLen = len(sanS)
c = r = 0
p = [0] * sanSLen
for i in range(1, sanSLen - 1):
i_mirror = 2 * c - i
# si la nueva posicion esta dentro de los confines del palindromo actual
# podemos hacer un par de cosas para acelerar el analisis del palindromo
# si en la posicion espejo hay un palindromo entonces en la posicion actual tambien
# pero no podemos suponer lo que hay mas alla de R, asi que si al copiar la
# longitud del palindromo espejo a la posicion actual se sobrepasa la frontera
# de R entonces solo se puede copiar con certeza que hay un palindromo desde
# la posición actual hasta la frontera explorada R
if i < r:
p[i] = min(r - i, p[i_mirror])
# toma a i como el posible centro de un palindromo
# y compara el simbolo de la derecha con el de la izquierda
# si son iguales se marca que i es el centro de un palindromo de radio 1
# se vuelve a comparar pero ahora a 2 simbolos de distancia a cada lado
# si son iguales se marca que i es el centro de un palindromo de radio 2
# se sigue comparando hasta que el simbolo de X posiciones a la derecha
# ya no es igual al simbolo de X posiciones a la izquierda
while sanS[i + 1 + p[i]] == sanS[i - 1 - p[i]]:
p[i] += 1
# si la posicion actual es el centro de un palindromo confirmado
# (porque el radio es mayor a cero) entonces se establece
# el limite derecho como la posicion actual mas el radio
# del palindromo del cual i es el centro
# se establece i como el centro del palindromo analizado
if i + p[i] > r:
c = i
r = i + p[i]
# posicion del radio mayor
max_index, max_value = max(enumerate(p), key=lambda x: x[1])
palindrom = sanS[max_index - max_value:max_index + max_value + 1]
# quitamos los simbolos auxiliares
return palindrom.replace("$", "").replace(symbol, "").replace('@', "")Está solución tomó 39ms y es mejor que el 98% de la soluciones enviadas. Me da curiosidad el ese 2% de soluciones mejores que esta pero mejor lo dejo hasta aquí.
Comentarios
Publicar un comentario