Palindrome Partitioning

Q: Quelle est la complexité temporelle du partitionnement en palindromes ?

Sur une chaîne composée de lettres identiques, les 2^(n-1) découpages sont tous des réponses, chacune pouvant contenir jusqu’à 2n-1 caractères : O(n × 2^n) . Aucune méthode ne fait mieux, car écrire la réponse coûte autant. La table des palindromes ajoute un temps et un espace de O(n²) , et la récursion O(n) .

Q: Combien de partitions en palindromes une chaîne peut-elle avoir ?

Au plus 2^(n-1) , une pour chaque façon de choisir lesquelles des n-1 espaces découper. Une chaîne de lettres identiques atteint cette limite : 1 024 découpages pour 11 lettres. Une chaîne sans lettres répétées n’a qu’un seul découpage, chaque lettre étant seule.

Q: Le problème de partitionnement de palindrome relève-t-il de la programmation dynamique ou du retour arrière ?

Il utilise les deux. Énumérer jusqu’à 2^(n-1) découpages nécessite une recherche qui construit chaque découpage pièce par pièce : du retour arrière. La programmation dynamique fournit le tableau de oui ou non des sous-chaînes palindromiques consulté par la recherche, rempli une seule fois en O(n²) .

MoyenRetour sur trace Programmation dynamique

+10

Un palindrome se lit de la même façon de gauche à droite et de droite à gauche. Découpe la chaîne s en une ou plusieurs parties de sorte que chaque partie soit un palindrome, puis renvoie toutes les façons de le faire.

Écris chaque découpage sous la forme de ses parties dans l’ordre, séparées par | : découper aab en a, a et b donne a|a|b. Renvoie les découpages par ordre croissant, en comparant les codes des caractères, de sorte que | vient après toutes les lettres minuscules.

Fonction

partition(s: string) → string-array

sstring: la chaîne de lettres minuscules à découper
Renvoiestring-array: chaque découpage de s en palindromes, avec | entre les morceaux, par ordre croissant

Contraintes

1 ≤ s.length ≤ 11
s ne contient que des lettres minuscules anglaises.
Une chaîne de 11 lettres identiques comporte 1,024 découpages, la réponse la plus grande.

Exemples

Entrée: s = "aab"
Sortie: ["aa|b", "a|a|b"]
Explication: Seuls aa|b et a|a|b ont uniquement des morceaux palindromiques ; a|ab échoue pour ab. aa|b vient en premier dans l’ordre de tri : au deuxième caractère, il a a alors que l’autre a |, qui vient après toutes les lettres dans l’ordre de tri.

Entrée: s = "abba"
Sortie: ["abba", "a|bb|a", "a|b|b|a"]
Explication: abba est lui-même un palindrome, donc la chaîne non découpée est une partition et vient en premier : son deuxième caractère est une lettre. a|bb|a vient avant a|b|b|a : au quatrième caractère, elle a b là où l’autre a |.

Pour aller plus loin

Peux-tu trouver le nombre minimal de coupures qui divise s en palindromes, pour des chaînes d’une longueur maximale de 2 000 ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chacun des n-1 espaces entre les lettres est coupé ou non, donc il y a 2^(n-1) découpages, et chacun d’eux peut être une réponse. Tu ne peux pas réduire la taille de la sortie, mais tu peux ignorer les découpages qui échouent : construis chaque découpage de gauche à droite, ne coupe que des morceaux palindromiques et lis les palindromes dans une table remplie une seule fois.

Essayez chaque ensemble de coupes

Intuition

Numérote les découpages avec les entiers de 0 à 2^(n-1)-1, chaque bit indiquant si une coupure est effectuée à un intervalle. Garde un nombre si chacune de ses parties est un palindrome.

Si l’intervalle initial correspond au bit de poids fort, le décompte croissant énumère les découpages dans l’ordre croissant. Pour deux nombres, le bit de poids fort où ils diffèrent correspond au premier intervalle où l’un effectue une coupure et l’autre non. Avant cet intervalle, les chaînes sont identiques ; à cet endroit, le plus petit nombre a une lettre et le plus grand a |, qui se classe après toutes les lettres. Pour aab, 1 donne aa|b et 3 donne a|a|b.

Avec 11 lettres, cela fait 1 024 masques de 11 lettres chacun. Le gaspillage vient des découpages rejetés : abcdefghijk en construit 1 024 pour trouver une réponse.

Algorithme

Parcourez mask de 0 à 2^(n-1)-1.
Parcourez les lettres ; terminez une partie après la lettre i lorsque i est le dernier indice ou que le bit n-2-i de mask est activé.
Vérifiez chaque partie à l’aide de deux pointeurs qui se déplacent vers l’intérieur.
Si chaque partie est un palindrome, joignez les parties avec | et ajoutez la chaîne à la réponse.
Renvoyez la réponse ; elle est déjà triée car la première coupure correspond au bit de poids fort.

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

Retour sur trace avec une table de palindromes

Intuition

La première partie est un préfixe palindrome s[0..end], et découper le reste revient au même problème à partir de end+1. Ainsi, backtrack(start) essaie chaque end pour lequel s[start..end] est un palindrome, ajoute la partie, lance un appel récursif, puis la retire. Chaque branche aboutit à une réponse, puisqu’une seule lettre est un palindrome, donc le travail suit la taille de la sortie : pour abcdefghijk, la recherche parcourt un seul chemin.

On vérifie dans de nombreuses branches si s[start..end] est un palindrome ; il faut donc lire cette information dans un tableau : s[i..j] vaut 1 lorsque s[i] == s[j] et que la partie intérieure s[i+1..j-1] vaut 1, ou lorsque la partie contient au plus 2 lettres.

Essayer end en partant du dernier indice donne une sortie triée. Deux découpages dont les premières parties diffèrent sont identiques jusqu’à la fin de la partie la plus courte ; à cet endroit, la plus courte a | et la plus longue a une lettre, donc la première partie la plus longue vient en premier dans l’ordre de tri.

Algorithme

Remplis pal[i][j] pour i de n-1 jusqu’à 0 : s[i] == s[j] et soit j-i < 2, soit pal[i+1][j-1].
Écris backtrack(start). Si start est égal à n, joins les morceaux actuels avec | et enregistre la chaîne.
Sinon, parcours end de n-1 jusqu’à start, et ignore-le sauf si pal[start][end].
Ajoute s[start..end] aux morceaux, appelle backtrack(end+1), puis retire le morceau.
Appelle backtrack(0) et renvoie les partitions enregistrées, déjà triées.

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

Pièges et cas limites

Essayer d’abord le morceau le plus court. Les découpages sont corrects, mais l’ordre ne l’est pas : a|a|b avant aa|b.
Trier à la fin avec une comparaison qui suit les règles linguistiques ou de locale, ce qui peut placer | avant les lettres. Comparez les codes des caractères ou générez les découpages dans l’ordre.
Remplir le tableau des palindromes en faisant augmenter i. pal[i+1][j-1] est alors lu avant d’être calculé ; faites décroître i à partir de n-1.
Mélanger un end inclusif et une fin de sous-chaîne exclusive. Le morceau s[start..end] contient end-start+1 lettres.
Enregistrer la liste partagée des morceaux au lieu de la chaîne assemblée. La recherche continue de modifier cette liste, donc toutes les entrées enregistrées finissent par être identiques.

Questions fréquentes3

Quelle est la complexité temporelle du partitionnement en palindromes ?

Sur une chaîne composée de lettres identiques, les 2^(n-1) découpages sont tous des réponses, chacune pouvant contenir jusqu’à 2n-1 caractères : O(n × 2^n). Aucune méthode ne fait mieux, car écrire la réponse coûte autant. La table des palindromes ajoute un temps et un espace de O(n²), et la récursion O(n).

Combien de partitions en palindromes une chaîne peut-elle avoir ?

Au plus 2^(n-1), une pour chaque façon de choisir lesquelles des n-1 espaces découper. Une chaîne de lettres identiques atteint cette limite : 1 024 découpages pour 11 lettres. Une chaîne sans lettres répétées n’a qu’un seul découpage, chaque lettre étant seule.

Le problème de partitionnement de palindrome relève-t-il de la programmation dynamique ou du retour arrière ?

Il utilise les deux. Énumérer jusqu’à 2^(n-1) découpages nécessite une recherche qui construit chaque découpage pièce par pièce : du retour arrière. La programmation dynamique fournit le tableau de oui ou non des sous-chaînes palindromiques consulté par la recherche, rempli une seule fois en O(n²).

def partition(s):
    # Écrivez le code ici

Test #1

Test #2

Argument

s = "aab"

Résultat attendu

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