Palindrome Partitioning II
Combine una tabla de palíndromos precalculada con PD unidimensional para encontrar el número mínimo de cortes necesarios para particionar una cadena en palíndromos.
Palindrome Partitioning II es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Problema: cortes mínimos para particionar
Palindrome Partitioning II plantea lo siguiente: dada la cadena s, encuentre el número mínimo de cortes necesarios para que cada subcadena de la partición sea un palíndromo. Para 'aab', un corte produce ['aa', 'b'], por lo que la respuesta es 1. Para 'a', la respuesta es 0 (ya es un palíndromo). Este problema combina dos fases de DP: primero se precalcula qué subcadenas son palíndromos y después se utiliza DP unidimensional para encontrar el número mínimo de cortes.
Fase 1: precalcular la tabla de palíndromos
Primero construya is_pal[i][j] = True si s[i..j] es un palíndromo mediante DP de intervalos. Esto se ejecuta en O(n²) de tiempo y O(n²) de espacio. Como alternativa, la expansión alrededor del centro puede rellenar la misma tabla en O(n²) de tiempo. Necesitamos esta tabla porque la DP unidimensional de cortes consultará is_pal[i][j] repetidamente; precalcularla evita volver a comprobar si una cadena es un palíndromo dentro del bucle de la DP de cortes.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))Fase 2: configurar la DP unidimensional de cortes
Defina cuts[i] como el número mínimo de cortes necesarios para particionar s[0..i]. Si s[0..i] es un palíndromo por sí misma, cuts[i] = 0. De lo contrario, pruebe cada división: para cada j de 0 a i-1, si s[j+1..i] es un palíndromo, entonces cuts[i] = min(cuts[i], cuts[j] + 1). La pregunta es: ¿qué ocurre si la última parte de la partición es s[j+1..i]? En ese caso, necesitamos cuts[j] cortes para el prefijo y un corte adicional.
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]Solución completa y recorrido
Hagamos el recorrido con 'aab'. Tabla de palíndromos: is_pal[0][0]='a'=T, is_pal[1][1]='a'=T, is_pal[2][2]='b'=T, is_pal[0][1]='aa'=T, is_pal[1][2]='ab'=F, is_pal[0][2]='aab'=F. Cortes: cuts[0]=0 ('a' es un palíndromo), cuts[1]=0 ('aa' es un palíndromo), cuts[2]: 'aab' no es un palíndromo; probamos j=1: is_pal[2][2]=T, por lo que cuts[2] = cuts[1]+1 = 1. Respuesta: 1.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))Complejidad temporal y espacial
La fase 1 (tabla de palíndromos) se ejecuta en O(n²) de tiempo y O(n²) de espacio. La fase 2 (DP de cortes) tiene un bucle externo sobre n posiciones y un bucle interno sobre n puntos de división, por lo que también requiere O(n²) de tiempo. En conjunto: O(n²) de tiempo y O(n²) de espacio. El espacio puede reducirse a O(n) para el arreglo de cortes, pero la tabla de palíndromos sigue requiriendo O(n²). En una entrevista se espera O(n²); una solución O(n) mediante Manacher's queda fuera del alcance habitual.
Expansión alrededor del centro para la tabla de palíndromos
En lugar del enfoque de DP de intervalos para construir la tabla de palíndromos, puede rellenar is_pal mediante la expansión alrededor del centro. Para cada posición central, expándase hacia ambos lados y marque todos los palíndromos encontrados. Sigue siendo O(n²) de tiempo y O(n²) de espacio, pero en la práctica puede ser más rápido gracias a un mejor comportamiento de la caché. Ambos enfoques son válidos en entrevistas.
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')Enumerar todas las particiones (Parte I)
Palindrome Partitioning I (un problema relacionado) pide enumerar TODAS las particiones válidas en las que cada subcadena sea un palíndromo. Para ello se utiliza backtracking junto con la tabla de palíndromos precalculada como mecanismo de poda. A diferencia de la DP de cortes mínimos, que cuenta las soluciones, este enfoque enumera un número exponencial de soluciones y se resuelve de una manera completamente distinta.
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]Inicializar cuts con n-1
Un truco habitual consiste en inicializar cuts[i] = i en lugar de inf, ya que el peor caso para s[0..i] es cortar cada carácter por separado, lo que produce i cortes. Así se evita comprobar si el valor es inf en el código. Cuando is_pal[0][i] es verdadero, se sobrescribe con 0. Esta inicialización aclara el límite superior de cortes y simplifica ligeramente el código.
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]Alternativa: DP en una sola pasada sin tabla separada
Una variante elegante rellena simultáneamente la tabla de palíndromos y la DP de cortes. A medida que expandimos los palíndromos desde cada centro, actualizamos de inmediato el arreglo cuts. Para un palíndromo s[l..r], podemos actualizar cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Esto evita una pasada independiente por la tabla O(n²) y puede resultar más fácil de implementar durante una entrevista bajo presión de tiempo.
Casos límite que debe considerar
Casos límite importantes para Palindrome Partitioning II: (1) una cadena de un solo carácter devuelve 0 cortes; (2) una cadena que ya es un palíndromo devuelve 0 cortes; (3) una cadena cuyos caracteres son todos distintos necesita n-1 cortes; (4) una cadena formada por caracteres idénticos (por ejemplo, 'aaaa') necesita 0 cortes, ya que toda la cadena es un palíndromo. Verifique siempre que su solución gestione correctamente la salida temprana cuando is_pal[0][i] = True.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2Consejos para comunicarse en una entrevista
Al presentar este problema en una entrevista, comience con el enfoque de dos fases: primero construya la tabla de palíndromos y después ejecute una DP unidimensional sobre el arreglo de cortes. Explique verbalmente la recurrencia antes de escribir el código. Mencione que la tabla de palíndromos tiene O(n²) entradas y que cada una se calcula en O(1) mediante la recurrencia de DP de intervalos. Antes de escribir la solución completa, recorra siempre el ejemplo paso a paso para demostrar que es correcta incluso bajo presión.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: Palindrome Partitioning II utiliza dos fases de DP: primero precalcula la tabla de palíndromos y después ejecuta una DP unidimensional de cortes, la recurrencia de cortes es cuts[i] = min(cuts[j-1] + 1) para todo j tal que s[j..i] sea un palíndromo, y la complejidad global es O(n²) de tiempo y O(n²) de espacio. A continuación abordaremos el problema Burst Balloons, que utiliza un ingenioso enfoque de DP de intervalos en sentido inverso.
Preguntas frecuentes
¿La lección «Palindrome Partitioning II» es gratis?
Sí — el texto completo de «Palindrome Partitioning II» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Palindrome Partitioning II»?
Combine una tabla de palíndromos precalculada con PD unidimensional para encontrar el número mínimo de cortes necesarios para particionar una cadena en palíndromos. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Palindrome Partitioning II»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Patrón de PD por intervalos y orden de llenado
- Subsecuencia y subcadena palindrómicas más largas
- Palindrome Partitioning II
- Burst Balloons: PD por intervalos en sentido inverso