Comment pouvez-vous trouver toutes les parens asymétriques dans une chaîne en temps linéaire avec une mémoire constante?

On m'a donné le problème suivant lors d'une interview:

Donne une chaîne qui contient un mélange de parens (pas de crochets ou d'accolades - seulement des parens) avec d'autres caractères alphanumériques, identifiez toutes les parens qui n'ont pas de paren correspondant.

Par exemple, dans la chaîne ") (ab))", les indices 0 et 5 contiennent des parens qui n'ont pas de paren correspondant.

J'ai proposé une solution O (n) fonctionnelle utilisant la mémoire O (n), utilisant une pile et parcourant la chaîne une fois en ajoutant des parens à la pile et en les supprimant de la pile chaque fois que je rencontrais un paren de fermeture et le haut de la pile contenue un paren d'ouverture.

Ensuite, l'intervieweur a noté que le problème pouvait être résolu en temps linéaire avec une mémoire constante (comme dans, pas d'utilisation de mémoire supplémentaire en plus de ce qui est absorbé par l'entrée.)

J'ai demandé comment et elle a dit quelque chose sur le fait de parcourir la chaîne une fois par la gauche en identifiant toutes les parens ouvertes, puis une deuxième fois en partant de la droite en identifiant toutes les parens proches ... ou peut-être que c'était l'inverse. Je ne comprenais pas vraiment et je ne voulais pas lui demander de me tenir par la main.

Quelqu'un peut-il clarifier la solution qu'elle a suggérée?

Comme cela vient d'un contexte de programmation et non d'un exercice informatique théorique, je suppose qu'il faut de la mémoire pour stocker un index dans la chaîne. En informatique théorique, cela signifierait utiliser le modèle RAM; avec les machines Turing, vous ne pouviez pas faire cela et vous auriez besoin de la mémoire pour stocker un index dans une chaîne de longueur .$O(1)$$\Theta(\log(n))$$n$

Vous pouvez conserver le principe de base de l'algorithme que vous avez utilisé. Vous avez raté une opportunité d'optimisation de la mémoire.

en utilisant une pile et en parcourant la chaîne une fois en ajoutant des parens à la pile et en les supprimant de la pile chaque fois que je rencontrais une paren de fermeture et que le haut de la pile contenait une paren d'ouverture

Alors, que contient cette pile? Il ne contiendra jamais ()(une parenthèse ouvrante suivie d'une parenthèse fermante), car chaque fois que )vous apparaissez, vous sautez au (lieu de pousser le ). Ainsi, la pile est toujours de la forme )…)(…(- un tas de parenthèses fermantes suivi d'un tas de parenthèses ouvrantes.

Vous n'avez pas besoin d'une pile pour représenter cela. N'oubliez pas le nombre de parenthèses fermantes et le nombre de parenthèses ouvrantes.

Si vous traitez la chaîne de gauche à droite, à l'aide de ces deux compteurs, ce que vous avez à la fin est le nombre de parenthèses fermantes incompatibles et le nombre de parenthèses ouvrantes incompatibles.

Si vous souhaitez signaler les positions des parenthèses incompatibles à la fin, vous devez vous souvenir de la position de chaque parenthèse. Cela nécessiterait de la mémoire dans le pire des cas. Mais vous n'avez pas besoin d'attendre la fin pour produire une sortie. Dès que vous trouvez une parenthèse fermante non appariée, vous savez qu'elle n'est pas appariée, alors éditez-la maintenant. Et puis vous n'allez pas utiliser le nombre de parenthèses fermantes incompatibles pour quoi que ce soit, alors gardez simplement un compteur de parenthèses ouvrantes inégalées.$\Theta(n)$

En résumé: traitez la chaîne de gauche à droite. Maintenez un compteur de parenthèses ouvrantes inégalées. Si vous voyez une parenthèse ouvrante, incrémentez le compteur. Si vous voyez une parenthèse fermante et que le compteur est différent de zéro, décrémentez le compteur. Si vous voyez une parenthèse fermante et que le compteur est égal à zéro, sortez l'index actuel sous la forme d'une parenthèse fermante incompatible.

La valeur finale du compteur est le nombre de parenthèses ouvrantes incompatibles, mais cela ne vous donne pas leur position. Notez que le problème est symétrique. Pour répertorier les positions des parenthèses ouvrantes incompatibles, exécutez simplement l'algorithme dans la direction opposée.

Exercice 1: notez-le dans une notation formelle (mathématiques, pseudocode ou votre langage de programmation préféré).

Exercice 2: Convainquez- vous qu'il s'agit du même algorithme que Apass.Jack , juste expliqué différemment.

Puisque nous pouvons simplement ignorer tous les caractères alphanumériques, nous supposerons que la chaîne ne contient désormais que des parenthèses. Comme dans la question, il n'y a qu'un seul type de parenthèse, "()".

Si nous continuons à supprimer les parenthèses équilibrées jusqu'à ce qu'aucune parenthèse plus équilibrée ne puisse être supprimée, toutes les parenthèses restantes doivent ressembler à ")) ...) ((... (", qui sont toutes des parenthèses non équilibrées. Cette observation suggère que nous devrions d'abord trouver ce point tournant). , avant lesquelles nous n'avons que des parenthèses fermantes asymétriques et après quoi nous avons uniquement des parenthèses ouvrantes asymétriques.

Voici l'algorithme. En un mot, il calcule d'abord le point tournant. Ensuite, il sort des parenthèses fermantes supplémentaires, balayant la chaîne du début vers la droite jusqu'au tournant. Symétriquement, il sort des parenthèses ouvrantes supplémentaires, balayant de la fin vers la gauche jusqu'au tournant.

str$n$

Initialisez turning_point=0, maximum_count=0, count=0. Pour chacun ide 0de n-1faire ce qui suit.

1. Si str[i] = ')', ajoutez 1 à count; sinon, soustrayez 1.
2. Si count > maximum_count, réglez turning_point=iet maximum_count=count.

C'est maintenant turning_pointl'indice du tournant.

Réinitialiser maximum_count=0, count=0. Pour chacun ide 0de turning_pointfaire ce qui suit.

1. Si str[i] = ')', ajoutez 1 à count; sinon, soustrayez 1.
2. Si count > maximum_count, réglez maximum_count = count. Sortie en itant qu'index d'une parenthèse fermante non équilibrée.

Réinitialiser maximum_count=0, count=0. Pour chacun ide n-1vers le turning_point+1bas, procédez comme suit.

1. Si str[j] = '(', ajoutez 1 à count; sinon, soustrayez 1.
2. Si count > maximum_count, réglez maximum_count = count. Sortie icomme index d'une parenthèse ouvrante non équilibrée.

$O(n)$$O(1)$$O(u)$$u$

Si nous avons analysé l'algorithme ci-dessus, nous verrons qu'en fait, nous n'avons pas du tout besoin de trouver et d'utiliser le point tournant. La belle observation que toutes les parenthèses fermantes asymétriques se produisent avant que toutes les parenthèses ouvrantes asymétriques puissent être ignorées bien qu'intéressantes.

Voici le code en Python .

Appuyez simplement sur «exécuter» pour voir plusieurs résultats de test.

Exercice 1. Montrez que l'algorithme ci-dessus produira un ensemble de parenthèses avec le moins de cardinalité de sorte que les parenthèses restantes soient équilibrées.

Problème 1. Pouvons-nous généraliser l'algorithme au cas où la chaîne contient deux types de parenthèses telles que "() []"? Nous devons déterminer comment reconnaître et traiter la nouvelle situation, l'affaire entrelacée, "([)]".