Particionamento de palíndromos II
Combine uma tabela de palíndromos pré-calculada com DP unidimensional para encontrar o número mínimo de cortes necessários para particionar uma string em palíndromos.
Particionamento de palíndromos II é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Problema: cortes mínimos para particionar
Particionamento de Palíndromos II pergunta: dada a cadeia de caracteres s, encontre o número mínimo de cortes para que cada subcadeia da partição seja um palíndromo. Para 'aab', um corte produz ['aa', 'b'], portanto a resposta é 1. Para 'a', a resposta é 0 (já é um palíndromo). Este problema combina duas fases de DP: primeiro, pré-computar quais subcadeias são palíndromos; depois, usar DP unidimensional para encontrar o número mínimo de cortes.
Fase 1: pré-computação da tabela de palíndromos
Primeiro, construa is_pal[i][j] = True se s[i..j] for um palíndromo, usando DP de intervalos. Isso é executado em tempo O(n²) e espaço O(n²). Como alternativa, a expansão ao redor do centro preenche a mesma tabela em tempo O(n²). Precisamos dessa tabela porque o DP unidimensional de cortes consultará is_pal[i][j] repetidamente — a pré-computação evita refazer as verificações de palíndromos dentro do laço do 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: configuração do DP unidimensional de cortes
Defina cuts[i] como o número mínimo de cortes para particionar s[0..i]. Se s[0..i] for um palíndromo, cuts[i] = 0. Caso contrário, tente todas as divisões: para cada j de 0 a i-1, se s[j+1..i] for um palíndromo, então cuts[i] = min(cuts[i], cuts[j] + 1). A pergunta é: e se a última parte da partição for s[j+1..i]? Nesse caso, precisaremos de cuts[j] cortes para o prefixo, mais 1 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]Solução completa e rastreamento
Vamos acompanhar o exemplo 'aab'. Tabela 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' é palíndromo), cuts[1]=0 ('aa' é palíndromo), cuts[2]: 'aab' não é palíndromo; tente j=1: is_pal[2][2]=T, portanto cuts[2] = cuts[1]+1 = 1. Resposta: 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'))Complexidade de tempo e espaço
A fase 1 (tabela de palíndromos) é executada em tempo O(n²) e espaço O(n²). A fase 2 (DP de cortes) tem um laço externo sobre n posições e um laço interno sobre n pontos de divisão, também com tempo O(n²). No total: tempo O(n²), espaço O(n²). O espaço pode ser reduzido para O(n) no vetor de cortes, mas a tabela de palíndromos ainda requer O(n²). Em entrevistas, espera-se O(n²) — uma solução O(n) usando o algoritmo de Manacher está além do escopo típico.
Expansão ao redor do centro para a tabela de palíndromos
Em vez da abordagem de DP de intervalos para a tabela de palíndromos, é possível preencher is_pal usando a expansão ao redor do centro. Para cada posição central, expanda para fora e marque todos os palíndromos encontrados. Isso ainda requer tempo O(n²) e espaço O(n²), mas pode ser mais rápido na prática devido à melhor localidade de referência na memória. As duas abordagens são válidas em 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')Enumeração de todas as partições (Parte I)
Particionamento de Palíndromos I (um problema relacionado) pede a enumeração de ALL partições válidas nas quais cada subcadeia é um palíndromo. Isso usa retrocesso, com a tabela de palíndromos pré-computada como um mecanismo de poda. Diferentemente do DP de cortes mínimos, que faz uma contagem, essa abordagem enumera um número exponencial de soluções e é resolvida de uma maneira completamente diferente.
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']]Inicializando cortes com n-1
Um truque comum é inicializar cuts[i] = i em vez de inf, pois o pior caso para s[0..i] é cortar cada caractere separadamente, resultando em i cortes. Isso evita verificar se há inf no código. Quando is_pal[0][i] é verdadeiro, substituímos o valor por 0. Essa inicialização esclarece o limite superior do número de cortes e simplifica um pouco o 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 em uma única passagem sem tabela separada
Uma variante elegante preenche simultaneamente a tabela de palíndromos e o DP de cortes. À medida que expandimos os palíndromos a partir de cada centro, atualizamos imediatamente o vetor cuts. Para um palíndromo s[l..r], podemos atualizar cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Isso evita uma passagem separada pela tabela O(n²) e pode ser mais simples de implementar durante uma entrevista sob pressão de tempo.
Casos extremos a considerar
Principais casos extremos do particionamento de palíndromos II: (1) uma cadeia de caracteres com um único caractere retorna 0 cortes; (2) uma cadeia de caracteres que já é um palíndromo retorna 0 cortes; (3) uma cadeia de caracteres com todos os caracteres distintos requer n-1 cortes; (4) uma cadeia de caracteres com todos os caracteres iguais (por exemplo, 'aaaa') requer 0 cortes, pois a cadeia inteira é um palíndromo. Verifique sempre se a solução trata corretamente a saída antecipada quando 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')) # 2Dicas de comunicação em entrevistas
Ao apresentar este problema em uma entrevista, comece pela abordagem em duas fases: primeiro construa a tabela de palíndromos, depois execute o DP unidimensional no vetor de cortes. Explique verbalmente a recorrência antes de escrever o código. Mencione que a tabela de palíndromos tem O(n²) entradas e que cada uma é preenchida em O(1) usando a recorrência do DP de intervalos. Antes de escrever a solução completa, percorra sempre o exemplo de rastreamento para demonstrar a correção sob pressão.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e & Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu: o particionamento de palíndromos II usa duas fases de DP — pré-computa a tabela de palíndromos e depois executa o DP unidimensional de cortes, a recorrência dos cortes é cuts[i] = min(cuts[j-1] + 1) para todo j em que s[j..i] é um palíndromo, e a complexidade total é tempo O(n²) e espaço O(n²). A seguir, abordaremos o problema dos Balões Explosivos, que usa uma abordagem inteligente de DP reversa de intervalos.
Perguntas Frequentes
A aula “Particionamento de palíndromos II” é grátis?
Sim — o texto completo de “Particionamento de palíndromos II” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Particionamento de palíndromos II”?
Combine uma tabela de palíndromos pré-calculada com DP unidimensional para encontrar o número mínimo de cortes necessários para particionar uma string em palíndromos. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Particionamento de palíndromos II”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Padrão de DP de intervalos e ordem de preenchimento
- Maior subsequência e substring palindrômicas
- Particionamento de palíndromos II
- Balões estourados: DP de intervalos reversa