Palindrome Partitioning

Q: ¿Cuál es la complejidad temporal de la partición de palíndromos?

En una cadena de letras iguales, las 2^(n-1) divisiones son respuestas, cada una de hasta 2n-1 caracteres: O(n × 2^n) . Ningún método puede superar eso, porque escribir la respuesta cuesta lo mismo. La tabla de palíndromos añade O(n²) de tiempo y espacio, y la recursión O(n) .

Q: ¿Cuántas particiones en palíndromos puede tener una cadena?

Como máximo, 2^(n-1) , una por cada forma de elegir cuáles de los n-1 espacios cortar. Una cadena de letras iguales alcanza ese límite: 1,024 divisiones para 11 letras. Una cadena sin letras repetidas tiene exactamente una división, cada letra por separado.

Q: ¿La partición de palíndromos es programación dinámica o retroceso?

Usa ambos. Enumerar hasta 2^(n-1) divisiones requiere una búsqueda que construya cada división pieza por pieza: retroceso. La programación dinámica proporciona la tabla de respuestas afirmativas o negativas de las subcadenas palindrómicas que lee la búsqueda, rellenada una sola vez en O(n²) .

MedioBacktracking Programación dinámica

+10

Un palíndromo se lee igual de izquierda a derecha y de derecha a izquierda. Divide la cadena s en una o más partes de modo que cada parte sea un palíndromo y devuelve todas las formas de hacerlo.

Escribe cada división con sus partes en orden, unidas por |: dividir aab en a, a y b da a|a|b. Devuelve las divisiones ordenadas en orden ascendente, comparando los códigos de los caracteres, de modo que | vaya después de todas las letras minúsculas.

Función

partition(s: string) → string-array

sstring: la cadena de letras minúsculas que se debe cortar
Devuelvestring-array: cada división de s en palíndromos, escritos con | entre las partes, en orden ascendente

Restricciones

1 ≤ s.length ≤ 11
s contiene solo letras minúsculas del alfabeto inglés.
Una cadena de 11 letras iguales tiene 1,024 divisiones, la respuesta más grande.

Ejemplos

Entrada: s = "aab"
Salida: ["aa|b", "a|a|b"]
Explicación: Solo aa|b y a|a|b tienen todas las partes palindrómicas; a|ab falla en ab. aa|b aparece primero al ordenar: en el segundo carácter tiene a, mientras que el otro tiene |, que se ordena después de todas las letras.

Entrada: s = "abba"
Salida: ["abba", "a|bb|a", "a|b|b|a"]
Explicación: abba es en sí mismo un palíndromo, así que la cadena sin cortar es una división y se ordena primero: su segundo carácter es una letra. a|bb|a va antes que a|b|b|a: en el cuarto carácter tiene b donde la otra tiene |.

Para ir más allá

¿Puedes encontrar el menor número de cortes que divide s en palíndromos, para cadenas de hasta 2.000 caracteres?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada uno de los n-1 espacios entre letras se corta o no, así que hay 2^(n-1) divisiones, y todas pueden ser respuestas. No puedes reducir el tamaño de la salida, pero puedes omitir las divisiones que no funcionan: construye cada división de izquierda a derecha, corta solo las partes palindrómicas y consulta los palíndromos en una tabla que se llena una sola vez.

Prueba cada conjunto de cortes

Intuición

Numera las divisiones con los enteros del 0 al 2^(n-1)-1; cada bit indica si se corta un espacio. Conserva la división de un número si cada parte es un palíndromo.

Si el primer espacio corresponde al bit de mayor valor, contar hacia arriba enumera las divisiones en orden ascendente. Para dos números, el bit de mayor valor en el que difieren corresponde al primer espacio donde uno corta y el otro no. Antes de ese espacio, las cadenas son iguales; allí, el número menor tiene una letra y el mayor tiene |, que se ordena después de cualquier letra. Para aab, 1 da aa|b y 3 da a|a|b.

Con 11 letras, eso supone 1,024 máscaras de 11 letras cada una. El desperdicio está en las divisiones descartadas: abcdefghijk genera las 1,024 para encontrar una respuesta.

Algoritmo

Recorre mask de 0 a 2^(n-1)-1.
Recorre las letras; termina una pieza después de la letra i cuando i sea el último índice o el bit n-2-i de mask esté establecido.
Comprueba cada pieza con dos punteros que se mueven hacia dentro.
Si cada pieza es un palíndromo, une las piezas con | y añade la cadena a la respuesta.
Devuelve la respuesta; ya está ordenada porque la primera separación corresponde al bit más significativo.

def partition(s):
    n = len(s)
    result = []
    # Bit (n-2-i) of mask says whether to cut after s[i]. Counting the
    # masks up from 0 lists the splits in sorted order.
    for mask in range(1 << (n - 1)):
        pieces = []
        start = 0
        for i in range(n):
            if i == n - 1 or (mask >> (n - 2 - i)) & 1:
                pieces.append(s[start:i + 1])
                start = i + 1
        if all(piece == piece[::-1] for piece in pieces):
            result.append("|".join(pieces))
    return result

Retroceso con una tabla de palíndromos

Intuición

La primera parte es un prefijo palindrómico s[0..end], y dividir el resto es el mismo problema a partir de end+1. Así que backtrack(start) prueba cada end donde s[start..end] es un palíndromo, añade la parte, vuelve a llamar recursivamente y la elimina. Cada rama termina en una respuesta, ya que una sola letra es un palíndromo, así que el trabajo depende del tamaño de la salida: para abcdefghijk, la búsqueda recorre un único camino.

Determinar si s[start..end] es un palíndromo se plantea en muchas ramas, así que se consulta en una tabla: s[i..j] es uno si s[i] == s[j] y el interior s[i+1..j-1] es uno, o si la parte tiene como máximo 2 letras.

Probar end desde el último índice hacia abajo produce una salida ordenada. Dos divisiones con partes iniciales distintas coinciden hasta el final de la parte más corta; ahí, la más corta tiene | y la más larga tiene una letra, así que la parte inicial más larga se ordena primero.

Algoritmo

Rellena pal[i][j] para i desde n-1 hasta 0: s[i] == s[j] y, o bien, j-i < 2 o bien pal[i+1][j-1].
Escribe backtrack(start). Si start es igual a n, une las partes actuales con | y guarda la cadena.
De lo contrario, recorre end desde n-1 hasta start y omítelo si no se cumple pal[start][end].
Añade s[start..end] a las partes, llama a backtrack(end+1) y luego elimina la parte.
Llama a backtrack(0) y devuelve las particiones guardadas, ya ordenadas.

def partition(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways.
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    result = []
    parts = []

    def backtrack(start):
        if start == n:
            result.append("|".join(parts))
            return
        # Longest piece first: "|" sorts after every letter, so a longer
        # first piece gives a smaller string and the output stays sorted.
        for end in range(n - 1, start - 1, -1):
            if pal[start][end]:
                parts.append(s[start:end + 1])
                backtrack(end + 1)
                parts.pop()

    backtrack(0)
    return result

Errores comunes y casos límite

Probar primero el fragmento más corto. Las particiones son correctas, pero el orden es incorrecto: a|a|b antes que aa|b.
Ordenar al final con una comparación que siga las reglas del idioma o la configuración regional, lo que puede colocar | antes que las letras. Compara los códigos de los caracteres o genera las particiones en orden.
Rellenar la tabla de palíndromos con i en orden ascendente. Entonces se lee pal[i+1][j-1] antes de calcularlo; rellena i desde n-1 hacia abajo.
Mezclar un end inclusivo con un final de subcadena exclusivo. El fragmento s[start..end] tiene end-start+1 letras.
Guardar la lista compartida de fragmentos en lugar de la cadena concatenada. La búsqueda sigue modificando esa lista, por lo que todas las entradas guardadas terminan siendo iguales.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de la partición de palíndromos?

En una cadena de letras iguales, las 2^(n-1) divisiones son respuestas, cada una de hasta 2n-1 caracteres: O(n × 2^n). Ningún método puede superar eso, porque escribir la respuesta cuesta lo mismo. La tabla de palíndromos añade O(n²) de tiempo y espacio, y la recursión O(n).

¿Cuántas particiones en palíndromos puede tener una cadena?

Como máximo, 2^(n-1), una por cada forma de elegir cuáles de los n-1 espacios cortar. Una cadena de letras iguales alcanza ese límite: 1,024 divisiones para 11 letras. Una cadena sin letras repetidas tiene exactamente una división, cada letra por separado.

¿La partición de palíndromos es programación dinámica o retroceso?

Usa ambos. Enumerar hasta 2^(n-1) divisiones requiere una búsqueda que construya cada división pieza por pieza: retroceso. La programación dinámica proporciona la tabla de respuestas afirmativas o negativas de las subcadenas palindrómicas que lee la búsqueda, rellenada una sola vez en O(n²).

def partition(s):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

s = "aab"

Salida Esperada

["aa|b", "a|a|b"]