Partitionnement palindromique II
Combinez une table de palindromes précalculée avec une DP en une dimension pour trouver le nombre minimal de coupures nécessaires afin de partitionner une chaîne en palindromes.
Partitionnement palindromique II est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Problème : nombre minimal de coupes pour partitionner
Partitionnement en palindromes II demande, étant donnée la chaîne s, de trouver le nombre minimal de coupes afin que chaque sous-chaîne de la partition soit un palindrome. Pour 'aab', une coupe donne ['aa', 'b'], la réponse est donc 1. Pour 'a', la réponse est 0 (la chaîne est déjà un palindrome). Ce problème combine deux phases de DP : précalculer d’abord les sous-chaînes qui sont des palindromes, puis utiliser une DP 1D pour trouver le nombre minimal de coupes.
Phase 1 : précalcul de la table des palindromes
Commencez par construire is_pal[i][j] = True si s[i..j] est un palindrome, en utilisant la DP par intervalles. Cette méthode s’exécute en temps O(n²) et avec un espace O(n²). Vous pouvez aussi remplir la même table par expansion autour du centre, en temps O(n²). Cette table est nécessaire, car la DP 1D des coupes consultera is_pal[i][j] à plusieurs reprises : le précalcul évite de refaire les vérifications de palindrome à l’intérieur de la boucle de la DP des coupes.
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'))Phase 2 : mise en place de la DP 1D des coupes
Définissez cuts[i] comme le nombre minimal de coupes pour partitionner s[0..i]. Si s[0..i] est lui-même un palindrome, cuts[i] = 0. Sinon, essayez chaque séparation : pour chaque j de 0 à i-1, si s[j+1..i] est un palindrome, alors cuts[i] = min(cuts[i], cuts[j] + 1). Nous cherchons à répondre à la question suivante : que se passe-t-il si la dernière partie de la partition est s[j+1..i] ? Il faut alors cuts[j] coupes pour le préfixe, plus une coupe supplémentaire.
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]Solution complète et traçage
Suivons l’exemple de 'aab'. Table des palindromes : 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. Coupes : cuts[0]=0 ('a' est un palindrome), cuts[1]=0 ('aa' est un palindrome), cuts[2] : 'aab' n’est pas un palindrome, essayons j=1 : is_pal[2][2]=T, donc cuts[2] = cuts[1]+1 = 1. Réponse : 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'))Complexité temporelle et spatiale
La phase 1 (table des palindromes) s’exécute en O(n²) et avec un espace O(n²). La phase 2 (DP des coupes) comporte une boucle externe sur n positions et une boucle interne sur n points de séparation, soit également un temps O(n²). Au total : temps O(n²), espace O(n²). L’espace utilisé par le tableau des coupes peut être réduit à O(n), mais la table des palindromes nécessite toujours O(n²). Les examinateurs attendent une complexité en O(n²) : une solution en O(n) utilisant l’algorithme de Manacher dépasse le cadre habituel.
Expansion autour du centre pour la table des palindromes
Au lieu de l’approche de DP par intervalles pour construire la table des palindromes, vous pouvez remplir is_pal par expansion autour du centre. Pour chaque position centrale, étendez-vous vers l’extérieur et marquez tous les palindromes trouvés. Cette méthode s’exécute toujours en temps O(n²) et avec un espace O(n²), mais elle peut être plus rapide en pratique grâce à un meilleur comportement du cache. Les deux approches sont valables en entretien.
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')Énumération de toutes les partitions (partie I)
Partitionnement en palindromes I (un problème connexe) demande d’énumérer toutes les partitions valides où chaque sous-chaîne est un palindrome. Cette méthode utilise une recherche avec retour arrière, la table précalculée des palindromes servant d’oracle d’élagage. Contrairement à la DP des coupes minimales, qui compte les solutions, elle en énumère un nombre exponentiel et se résout avec une approche entièrement différente.
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']]Initialisation de cuts avec n-1
Une astuce courante consiste à initialiser cuts[i] = i au lieu de inf, puisque dans le pire des cas pour s[0..i], chaque caractère doit être séparé, ce qui donne i coupes. Cela évite de vérifier la valeur inf dans votre code. Lorsque is_pal[0][i] vaut True, remplacez cette valeur par 0. Cette initialisation clarifie la borne supérieure du nombre de coupes et simplifie légèrement le code.
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]Alternative : DP en un seul passage sans table séparée
Une variante élégante remplit simultanément la table des palindromes et la DP des coupes. À mesure que vous développez les palindromes à partir de chaque centre, vous mettez immédiatement à jour le tableau cuts. Pour un palindrome s[l..r], vous pouvez mettre à jour cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Cela évite un passage séparé sur une table O(n²) et peut être plus simple à implémenter pendant un entretien soumis à une forte contrainte de temps.
Cas limites à prendre en compte
Voici les principaux cas limites du partitionnement en palindromes II : (1) une chaîne à un seul caractère renvoie 0 coupe ; (2) une chaîne qui est déjà un palindrome renvoie 0 coupe ; (3) une chaîne dont tous les caractères sont distincts nécessite n-1 coupes ; (4) une chaîne composée de caractères identiques (par ex. 'aaaa') nécessite 0 coupe, car la chaîne entière est un palindrome. Vérifiez toujours que votre solution gère correctement la sortie anticipée lorsque 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')) # 2Conseils de communication en entretien
Lors de la présentation de ce problème en entretien, commencez par l’approche en deux phases : construisez d’abord la table des palindromes, puis exécutez la DP 1D sur le tableau des coupes. Expliquez verbalement la récurrence avant de coder. Précisez que la table des palindromes contient O(n²) entrées et que chacune est remplie en O(1) à l’aide de la récurrence de la DP par intervalles. Parcourez toujours votre exemple de traçage avant d’écrire la solution complète, afin de démontrer sa correction sous pression.
Vérification rapide
Vérifiez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : le partitionnement en palindromes II utilise deux phases de DP — précalculer la table des palindromes, puis exécuter la DP 1D des coupes, la récurrence des coupes est cuts[i] = min(cuts[j-1] + 1) pour tout j tel que s[j..i] soit un palindrome, et la complexité globale est de O(n²) en temps et de O(n²) en espace. Nous allons ensuite aborder le problème des ballons à éclater, qui utilise une astucieuse DP par intervalles inversée.
Questions Fréquemment Posées
La leçon « Partitionnement palindromique II » est-elle gratuite ?
Oui — le texte complet de « Partitionnement palindromique II » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Partitionnement palindromique II » ?
Combinez une table de palindromes précalculée avec une DP en une dimension pour trouver le nombre minimal de coupures nécessaires afin de partitionner une chaîne en palindromes. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Partitionnement palindromique II » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Schéma de DP sur les intervalles et ordre de remplissage
- Plus longue sous-séquence et sous-chaîne palindromiques
- Partitionnement palindromique II
- Ballons à éclater : DP sur intervalles inversée