Wie erstelle ich für eine Zeichenfolge der Länge N mit den Zeichen [A-Z] das längste Palindrom für ein einzelnes Zeichen?
Ich werde dies an einem Beispiel illustrieren:
Gegebene Zeichenfolge: JOHNOLSON
Bei der Analyse der Zeichenfolge finden wir, dass wir ein Palindrom mit dem Zeichen O haben, sodass die Zeichenfolge wie folgt aussieht: J O HN O LS O N . Das Palindrom für die O hat die Länge 7 und sieht im Wesentlichen so aus: O -- O -- O . Beachten Sie auch, dass es ein Palindrom mit N gibt, aber es ist nur von der Länge 6.
Ein anderes Beispiel,
Gegebene Zeichenfolge: ABCJOHNOLSON gibt das gleiche Ergebnis wie oben mit einem Palindrom der O 's der Länge 7 aus, die wie O -- O aussieht -- O .
Mit der angegebenen Zeichenkette ABCJOHNOLSONDA hat das längste Palindrom mit individuellen Zeichen jedoch die Länge 14, wobei das Zeichen A wie folgt aussieht: A ------------ A .
Andere einfache Beispiele sind:
ABA - & gt; A - A (Länge 3)
ABAXYZ - & gt; A - A (Länge 3)
ABAXYZA - & gt; A --- A (Länge 5), nicht Länge 7, weil A - A --- A ist kein Palindrom für den Buchstaben A .
Achten Sie besonders auf das letzte Beispiel, da es eine der feinen Nuancen des Problems darstellt.
Sie können es in linearer Zeit tun, es wird hier mit einem Codebeispiel
Definitiv nicht optimal. Angenommen, die Eingabezeichenfolge ist kleingeschrieben.
%Vor%Tags und Links algorithm palindrome