Palindrome Partitioning

Q: Qual é a complexidade de tempo do particionamento de palíndromos?

Em uma string de letras iguais, todas as 2^(n-1) divisões são respostas, cada uma com até 2n-1 caracteres: O(n × 2^n) . Nenhum método supera isso, pois escrever a resposta custa o mesmo. A tabela de palíndromos acrescenta O(n²) de tempo e espaço, e a recursão, O(n) .

Q: Quantas partições em palíndromos uma string pode ter?

No máximo 2^(n-1) , uma para cada maneira de escolher quais dos n-1 intervalos cortar. Uma cadeia de letras iguais atinge esse limite: 1,024 divisões para 11 letras. Uma cadeia sem letras repetidas tem exatamente uma divisão, cada letra por si só.

Q: Palindromic Partitioning é programação dinâmica ou retrocesso?

Ele usa ambos. Listar até 2^(n-1) divisões exige uma busca que constrói cada divisão peça por peça: retrocesso. A programação dinâmica fornece a tabela de sim ou não dos substrings palíndromos que a busca consulta, preenchida uma única vez em O(n²) .

MédioBacktracking Programação dinâmica

+10

Um palíndromo é lido da mesma forma da esquerda para a direita e da direita para a esquerda. Divida a string s em uma ou mais partes, de modo que cada parte seja um palíndromo, e retorne todas as maneiras de fazer isso.

Escreva cada divisão com suas partes na ordem, separadas por |: dividir aab em a, a e b resulta em a|a|b. Retorne as divisões em ordem crescente, comparando os códigos dos caracteres, de modo que | venha depois de todas as letras minúsculas.

Função

partition(s: string) → string-array

sstring: a sequência de letras minúsculas a ser cortada
Retornastring-array: cada divisão de s em palíndromos, escrita com | entre as partes, em ordem crescente

Restrições

1 ≤ s.length ≤ 11
s contém apenas letras minúsculas do alfabeto inglês.
Uma string de 11 letras iguais tem 1.024 divisões, a resposta mais alta.

Exemplos

Entrada: s = "aab"
Saída: ["aa|b", "a|a|b"]
Explicação: Apenas aa|b e a|a|b têm todas as partes palindrômicas; a|ab falha em ab. aa|b vem primeiro na ordenação: no segundo caractere, ele tem a, enquanto o outro tem |, que vem depois de todas as letras.

Entrada: s = "abba"
Saída: ["abba", "a|bb|a", "a|b|b|a"]
Explicação: abba é um palíndromo, então a string sem cortes é uma divisão e vem primeiro na ordenação: seu segundo caractere é uma letra. a|bb|a vem antes de a|b|b|a: no quarto caractere, ela tem b, enquanto a outra tem |.

Para ir além

Você consegue encontrar o menor número de cortes que divide s em palíndromos, para strings de até 2.000 caracteres?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada um dos n-1 espaços entre as letras é cortado ou não, então há 2^(n-1) divisões, e todas elas podem ser respostas. Você não pode reduzir o tamanho da saída, mas pode pular as divisões que não funcionam: construa cada divisão da esquerda para a direita, corte apenas partes palíndromas e consulte os palíndromos em uma tabela preenchida uma única vez.

Experimente cada conjunto de cortes

Intuição

Numere as divisões com os inteiros de 0 a 2^(n-1)-1, cada bit indicando se um espaço é cortado. Mantenha um número de divisão se todas as partes forem palíndromos.

Se o primeiro espaço receber o bit mais significativo, contar para cima lista as divisões em ordem crescente. Para dois números, o bit mais significativo em que eles diferem corresponde ao primeiro espaço em que um corta e o outro não. Antes dele, as strings são iguais; nesse espaço, o número menor tem uma letra e o maior tem |, que vem depois de todas as letras na ordenação. Para aab, 1 resulta em aa|b e 3 resulta em a|a|b.

Com 11 letras, são 1.024 máscaras de 11 letras cada. O desperdício está nas divisões rejeitadas: abcdefghijk gera todas as 1.024 para encontrar uma resposta.

Algoritmo

Percorra mask de 0 a 2^(n-1)-1.
Percorra as letras; termine uma parte após a letra i quando i for o último índice ou o bit n-2-i de mask estiver definido.
Verifique cada parte com dois ponteiros que se movem para dentro.
Se todas as partes forem palíndromos, junte-as com | e adicione a string à resposta.
Retorne a resposta; ela já está ordenada porque a primeira separação corresponde ao bit mais 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

Retrocesso com uma tabela de palíndromos

Intuição

A primeira parte é um prefixo palindrômico s[0..end], e dividir o restante é o mesmo problema a partir de end+1. Portanto, backtrack(start) tenta cada end em que s[start..end] é um palíndromo, adiciona a parte, faz a chamada recursiva e a remove. Cada ramificação termina em uma resposta, pois uma única letra é um palíndromo, então o trabalho acompanha o tamanho da saída: para abcdefghijk, a busca percorre um caminho.

Como saber se s[start..end] é um palíndromo surge em muitas ramificações, consulte uma tabela: s[i..j] é um quando s[i] == s[j] e o trecho interno s[i+1..j-1] é um, ou quando a parte tem no máximo 2 letras.

Tentar end do último índice para baixo gera uma saída ordenada. Duas divisões com partes iniciais diferentes coincidem até o fim da parte mais curta; nesse ponto, a mais curta tem | e a mais longa tem uma letra, então a divisão com a parte inicial mais longa vem primeiro na ordenação.

Algoritmo

Preencha pal[i][j] para i de n-1 até 0: s[i] == s[j] e j-i < 2 ou pal[i+1][j-1].
Escreva backtrack(start). Se start for igual a n, junte as partes atuais com | e salve a string.
Caso contrário, percorra end de n-1 até start e ignore-o se pal[start][end] não for verdadeiro.
Adicione s[start..end] às partes, chame backtrack(end+1) e, em seguida, remova a parte.
Chame backtrack(0) e retorne as divisões salvas, já 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

Armadilhas e casos extremos

Tentar primeiro o menor trecho. As divisões estão corretas, mas a ordem está errada: a|a|b antes de aa|b.
Ordenar no final usando uma comparação que segue as regras do idioma ou da localidade, que pode colocar | antes das letras. Compare os códigos dos caracteres ou gere as divisões em ordem.
Preencher a tabela de palíndromos com i aumentando. pal[i+1][j-1] é lido antes de ser calculado; preencha i de n-1 até baixo.
Misturar um end inclusivo com um fim de substring exclusivo. O trecho s[start..end] tem end-start+1 letras.
Salvar a lista compartilhada de trechos em vez da string concatenada. A busca continua alterando essa lista, então todas as entradas salvas acabam iguais.

Perguntas frequentes3

Qual é a complexidade de tempo do particionamento de palíndromos?

Em uma string de letras iguais, todas as 2^(n-1) divisões são respostas, cada uma com até 2n-1 caracteres: O(n × 2^n). Nenhum método supera isso, pois escrever a resposta custa o mesmo. A tabela de palíndromos acrescenta O(n²) de tempo e espaço, e a recursão, O(n).

Quantas partições em palíndromos uma string pode ter?

No máximo 2^(n-1), uma para cada maneira de escolher quais dos n-1 intervalos cortar. Uma cadeia de letras iguais atinge esse limite: 1,024 divisões para 11 letras. Uma cadeia sem letras repetidas tem exatamente uma divisão, cada letra por si só.

Palindromic Partitioning é programação dinâmica ou retrocesso?

Ele usa ambos. Listar até 2^(n-1) divisões exige uma busca que constrói cada divisão peça por peça: retrocesso. A programação dinâmica fornece a tabela de sim ou não dos substrings palíndromos que a busca consulta, preenchida uma única vez em O(n²).

def partition(s):
    # Escreva o código aqui

Teste #1

Teste #2

Argumento

s = "aab"

Saída Esperada

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