Jemand hat uns eine Zeichenkette gegeben, aber alle Klammer-ähnlichen Zeichen wurden in normale Zeichen umgewandelt, und wir wissen nicht, welche oder wie viele es waren. Alles was wir wissen ist, dass wenn L1,L2,L3,...,LN
verschiedene Arten von linken Klammern und R1,R2,R3,...,RN
verschiedene entsprechende Arten von rechten Klammern vorhanden wären, die alle verschieden sind (2N verschiedene Klammerzeichen), eine Zeichenkette gültig wäre, wenn sie eine von (+ ist normale Zeichenkettenverkettung) ist:
L1+X+R1
,,L2+X+R2
...,,LN+X+RN
woX
ist eine gültige Zeichenfolge,X+Y
, woX
undY
sind gültige Zeichenfolgen,Jedes einzelne Zeichen, das kein Klammerzeichen ist.
Die leere Zeichenfolge
Wir wissen, dass sie mit einer gültigen Zeichenfolge begonnen haben, bevor sie die Klammern geändert haben, und sie haben sie nicht in Zeichen geändert, die bereits in der Zeichenfolge vorhanden waren. Auch für jede Klammer gab es mindestens ein Paar. Können Sie rekonstruieren, welche Zeichen ursprünglich linke und rechte Klammerpaare waren (finden Sie die Li
und Ri
nach den gegebenen Bedingungen)?
Geben Sie die Zeichenpaare aus, die Klammern waren. Wenn es sich beispielsweise (){}[]
tatsächlich um eckige Klammern handelt, können Sie (){}[]
oder {}[]()
oder [](){}
usw. ausgeben . Es gibt möglicherweise mehrere Möglichkeiten, dies für eine Zeichenfolge zu tun. Sie müssen nur eine zurückgeben, sodass keine eckige Klammer mit mehr Paaren vorhanden ist (siehe Beispiele). Beachten Sie, dass die Ausgabezeichenfolge immer eine gerade Länge haben sollte.
Beispiele:
abcc
- c
kann keine Klammer sein, da es kein anderes Zeichen mit zwei Vorkommen gibt, sondern ab
kann ein Klammerpaar sein, sodass Sie genau ausgeben würden ab
.
fffff
- Jeder String mit höchstens einem Zeichen darf keine eckigen Klammern enthalten. Sie würden also den leeren String zurückgeben oder nichts ausgeben.
aedbedebdcecdec
- Diese Zeichenfolge darf keine eckigen Klammern enthalten, da es 1 a, 2 bs, 3 cs, 4 ds und 5 es gibt, sodass keine zwei Zeichen gleich oft vorkommen. Dies ist eine Voraussetzung für eckige Klammern.
abcd
- mögliche Zuordnungen sind ab
, cd
, abcd
, cdab
, adbc
, bcad
, ac
, ad
, bc
und bd
, (sowie die leere Zuordnung, die alle von ihnen haben) , aber Sie müssen eine der längsten Zuweisungen zurückkehren, so dass Sie zurückkehren müssen abcd
, cdab
, adbc
, oder bcad
.
aabbcc
, abc
- diese haben beide ab
, ac
und bc
als gültige Paare. Sie müssen eines dieser Paare zurückgeben, egal welches.
abbac
- a und b haben die gleiche Zeichenanzahl, können aber nicht funktionieren, da eines von ihnen links und rechts von allen Vorkommen des anderen vorkommt. Nichts zurückgeben.
aabcdb
- cd
und ab
sind die genau zwei Klammerpaare, also entweder cdab
oder ausgeben abcd
.
abcdacbd
- nur ein Paar auf einmal erreicht werden, aber ab
, ac
, bd
, cd
, und ad
werden alle möglichen Paare können Sie zurückkommen . Egal , welches Paar Sie sich entscheiden, hat es eine Instanz , wo eine einzige andere Zeichen in ihm ist, die alle anderen Paare verbietet, außer im Fall ad
, wo die anderen Paare bc
und cb
sind nicht möglich allein entweder, und so nicht möglich sein kann , mit ad
.
Dies ist Code Golf, also gewinnt der kürzeste Code in Bytes. Die Eingabe erfolgt von STDIN, wenn dies für Ihre Sprache möglich ist. Wenn dies nicht möglich ist, geben Sie in Ihrer Antwort die Eingabemethode an.
quelle
abcd
die eingabeadbc
wäre die ausgabe auch akzeptabel, oder?Antworten:
Ruby, 373 Bytes
Dieser verwendet eine golfed Version des Stapels Parser hier .
Es kann wahrscheinlich weiter vereinfacht werden, aber ich glaube nicht, dass mein Gehirn mehr damit fertig wird.
Alle Testfälle: http://ideone.com/gcqDkK
Mit Leerzeichen: http://ideone.com/pLrsHg
Ungolfed (meistens): http://ideone.com/oM5gKX
quelle