[LeetCode] 0005. Subcadena palindrómica más larga

				
					Complejidad temporal de #: O(n) Complejidad espacial de #: O(n) Solución de la clase Algoritmo de Manacher: def longestPalindrome(self, s: str) -> str: sPrime = "#" + "#".join(s) + "#" n = len(sPrime) palindromeRadii = [0] * n center = radio = 0 para i en range(n): espejo = 2 * centro - i si i < radio: palindromeRadii[i] = min(radio - i, palindromeRadii[mirror]) mientras ( i + 1 + palindromeRadii[i] < n y i - 1 - palindromeRadii[i] >= 0 y sPrime[i + 1 + palindromeRadii[i]] == sPrime[i - 1 - palindromeRadii[i]] ): palindromeRadii[i] += 1 si i + palindromeRadii[i] > radio: centro = i radio = i + palindromeRadii[i] longitudmáx = máx(palindromeRadii) índiceCentro = palindromeRadii.index(longitudmáx) índiceInicio = (índiceCentro - longitudmáx) // 2 longestPalindrome = s[índiceInicio: índiceInicio + longitudmáx] devolver longestPalindrome # Fuerza bruta # complejidad de tiempo: O(n^3) # complejidad de espacio: O(n^3) Solución de clase: def longestPalindrome(self, s: str) -> str: def check(i, j): izquierda = i derecha = j - 1 mientras izquierda < derecha: si s[izquierda] != s[derecha]: devolver Falso izquierda += 1 derecha -= 1 devuelve Verdadero para longitud en rango(len(s), 0, -1): para inicio en rango(len(s) - longitud + 1): si check(inicio, inicio + longitud): devuelve s[inicio: inicio + longitud] devuelve "" # complejidad de tiempo: O(n^2) # complejidad de espacio: O(n^2) # Solución de clase de programación dinámica: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[Falso] * n para _ en rango(n)] ans = [0, 0] para i en rango(n): dp[i][i] = Verdadero para i en rango(n-1): si s[i] == s[i+1]: dp[i][i+1] = Verdadero ans = [i, i+1] para diff en rango(2, n): para i en rango(n - diff): j = i + diff si s[i] == s[j] y dp[i+1][j-1]: dp[i][j] = Verdadero ans = [i, j] i, j = ans devuelve s[i:j+1] s = "babad" print(Solution().longestPalindrome(s)) s = "cbbd" print(Solution().longestPalindrome(s))