Valid Palindrome

Q: Wie hoch ist die Zeitkomplexität von Valid Palindrome?

Beide Ansätze laufen in O(n) -Zeit, da jedes Zeichen eine konstante Anzahl von Malen betrachtet wird. Das vorherige Bereinigen benötigt für die Kopie zusätzlichen Speicherplatz von O(n) . Die Version mit zwei Zeigern benötigt zusätzlichen Speicherplatz von O(1) , da sie nur zwei Indizes speichert.

Q: Wie prüfst du, ob etwas ein Palindrom ist, wenn du nicht alphanumerische Zeichen ignorierst?

Behalte an jedem Ende der Zeichenfolge einen Zeiger. Bewege einen Zeiger über jedes Zeichen hinweg, das kein Buchstabe und keine Ziffer ist. Wenn beide auf Buchstaben oder Ziffern zeigen, vergleiche sie in Kleinbuchstaben. Wenn jedes verglichene Paar übereinstimmt, bis sich die Zeiger treffen, ist die Zeichenfolge ein Palindrom.

Q: Ist eine leere Zeichenfolge ein Palindrom?

Ein leerer Text ist in beiden Richtungen gleich, daher gibt eine Zeichenfolge wie ?!-_ , deren Zeichen alle ignoriert werden, true zurück. Beide Ansätze erreichen dies ohne zusätzlichen Code: Der bereinigte Text entspricht seiner umgekehrten Version, und die beiden Zeiger finden nie ein Paar, das sich unterscheidet.

Q: Warum zwei Zeiger verwenden, anstatt die Zeichenkette umzukehren?

Das Umkehren erfordert eine bereinigte Kopie und eine umgekehrte Kopie, was O(n) zusätzlichen Speicherplatz benötigt. Zwei Zeiger vergleichen dieselben Paare direkt und können beim ersten Unterschied anhalten, oft schon nach wenigen Schritten. Interviewer fragen als Folgefrage meist nach dieser Variante.

LeichtZwei Zeiger

+10

Du erhältst eine Zeichenfolge s. Behalte nur ihre Buchstaben und Ziffern bei, behandle Groß- und Kleinbuchstaben als denselben Buchstaben und entscheide, ob das Übriggebliebene von links nach rechts genauso gelesen wird wie von rechts nach links. Gib true zurück, wenn das der Fall ist, andernfalls false.

Alle anderen Zeichen, wie ., !, ?, :, ;, - oder _, werden ignoriert. Wenn s überhaupt keine Buchstaben oder Ziffern enthält, bleibt nichts übrig, und ein leerer Text gilt als Palindrom.

Funktion

isPalindrome(s: string) → boolean

sstring: der zu prüfende Text, einschließlich der Zeichensetzung
Gibt zurückboolean: wahr, wenn die Buchstaben und Ziffern von s in beide Richtungen gleich gelesen werden, wobei die Groß- und Kleinschreibung ignoriert wird

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält englische Buchstaben, Ziffern und die Satzzeichen . ! ? : ; - _, ohne Leerzeichen.

Beispiele

Eingabe: s = "Was_it_a_car_or_a_cat_I_saw?"
Ausgabe: true
Erklärung: Lässt man die Unterstriche und das Fragezeichen weg und schreibt die Großbuchstaben klein, erhält man wasitacaroracatisaw, was rückwärts genauso aussieht.

Eingabe: s = "race-a-car"
Ausgabe: false
Erklärung: Ohne die Bindestriche lautet der Text raceacar. Von rechts gelesen beginnt er mit raca statt mit race: Das e in der Mitte hat ein a als Spiegelpartner, daher lautet die Antwort false.

Eingabe: s = "Step-on-no-pets!"
Ausgabe: true
Erklärung: Der beibehaltene Text ist steponnopets. Das große S stimmt mit dem abschließenden s überein, da die Groß- und Kleinschreibung ignoriert wird, und die Bindestriche sowie das ! spielen keine Rolle.

+25 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du das mit O(1) zusätzlichem Speicherplatz entscheiden, ohne eine bereinigte Kopie von s zu erstellen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Palindromprüfung selbst ist die bekannte: Das erste beibehaltene Zeichen muss dem letzten entsprechen, das zweite dem vorletzten und so weiter. Knifflig an dieser Version ist, dass die verglichenen Zeichen nicht an gespiegelten Indizes von s stehen, weil Satzzeichen auf beiden Seiten ungleichmäßig verteilt sind. Du kannst sie zuerst entfernen oder zwei Zeiger beim Aufeinanderzugehen darüber hinwegsetzen lassen.

Bereinige die Zeichenkette und vergleiche sie dann mit ihrer Umkehrung

Idee

Erzeuge den Text, nach dem die Aufgabe tatsächlich fragt. Durchlaufe s, behalte jeden Buchstaben und jede Ziffer in Kleinbuchstaben bei und überspringe alles andere. Für Step-on-no-pets! ergibt das steponnopets. Jetzt stellt sich die ganz gewöhnliche Palindromfrage: Ist dieser Text gleich seiner Umkehrung?

Das ist korrekt, weil beim Bereinigen genau die Zeichen entfernt werden, die laut Aufgabenstellung ignoriert werden sollen, und die Groß- und Kleinschreibung vereinheitlicht wird, die ignoriert werden soll. Wenn s keine Buchstaben oder Ziffern enthält, ist der bereinigte Text leer. Ein leerer Text ist gleich seiner Umkehrung, also lautet die Antwort ohne Sonderfall true.

Jedes Zeichen wird einmal zum Bereinigen und ein weiteres Mal zum Vergleichen gelesen, daher beträgt die Laufzeit O(n). Die bereinigte Kopie und ihre Umkehrung benötigen zusätzlich O(n) Speicher, den der nächste Ansatz einspart.

Algorithmus

Erstelle einen leeren Text cleaned.
Füge für jedes Zeichen von s das Zeichen in Kleinbuchstaben hinzu, wenn es ein Buchstabe oder eine Ziffer ist.
Kehrt cleaned um.
Gib zurück, ob cleaned mit seiner Umkehrung übereinstimmt.

def isPalindrome(s):
    cleaned = [ch.lower() for ch in s if ch.isalnum()]
    return cleaned == cleaned[::-1]

Zwei Zeiger, die Satzzeichen überspringen

Idee

Die bereinigte Kopie ist nur dazu da, damit du gespiegelte Zeichen vergleichen kannst. Du kannst denselben Vergleich auch direkt auf s durchführen. Setze left auf den ersten Index und right auf den letzten. Wenn bei einem Schritt left auf ein Satzzeichen zeigt, bewege ihn nach rechts; zeigt right auf ein Satzzeichen, bewege ihn nach links. Sobald beide auf Buchstaben oder Ziffern zeigen, vergleiche sie in Kleinbuchstaben. Bei einer Abweichung ist das Ergebnis false; stimmen sie überein, bewegen sich beide Zeiger nach innen.

Warum ist dies dieselbe Prüfung? Die Zeiger halten immer beim nächsten beibehaltenen Zeichen von jedem Ende an. Daher durchlaufen sie die Paare (erstes beibehaltenes, letztes beibehaltenes), (zweites beibehaltenes, vorletztes beibehaltenes) und so weiter – genau die Paare, die auch beim Vergleich mit der umgekehrten Zeichenfolge betrachtet werden. In Abc-dcbX ist das erste Paar A und X, und nach einem Vergleich lautet das Ergebnis false.

Bei jedem Schritt wird mindestens ein Zeiger bewegt, und sie halten an, wenn sie sich treffen, daher wird die Schleife höchstens n-mal ausgeführt. Außer den beiden Indizes wird nichts gespeichert, was einen zusätzlichen Speicherbedarf von O(1) ergibt.

Algorithmus

Setze left = 0 und right = n-1.
Solange left < right gilt: Wenn s[left] kein Buchstabe oder keine Ziffer ist, erhöhe left und fahre fort.
Andernfalls: Wenn s[right] kein Buchstabe oder keine Ziffer ist, verringere right und fahre fort.
Vergleiche andernfalls die beiden Zeichen in Kleinbuchstaben. Wenn sie unterschiedlich sind, gib false zurück; wenn sie übereinstimmen, bewege beide Zeiger nach innen.
Wenn sich die Zeiger treffen, gib true zurück.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1
        elif not s[right].isalnum():
            right -= 1
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen durch Zeichen, die übersprungen werden, und durch Groß- und Kleinschreibung.

s[i] mit s[n-1-i] in der unveränderten Zeichenfolge vergleichen. a-ba ist ein Palindrom, sobald der Bindestrich entfernt wird, aber das Spiegelbild von - an Index 1 ist in der unveränderten Zeichenfolge das b an Index 2.
Beide Zeiger verschieben, obwohl nur einer davon auf einem Satzzeichen steht. Überspringe jeweils nur auf einer Seite, sonst geraten die beiden Seiten aus dem Takt.
Satzzeichen in einer inneren Schleife überspringen, die über den anderen Zeiger hinausläuft. Bei ?!-_ läuft eine unbeschränkte innere Schleife über das Ende der Zeichenfolge hinaus; prüfe bei jeder Bewegung left < right.
Ziffern als unwichtig behandeln. 0P ist false: Die Ziffer 0 bleibt erhalten und wird verglichen; sie ist nicht der Buchstabe p.
false zurückgeben, wenn nichts übrig bleibt. Eine Zeichenfolge, die nur aus Satzzeichen besteht, etwa ., hat einen leeren bereinigten Text, der ein Palindrom ist.
Eine Zeichenfolge, die nur aus Ziffern besteht, etwa 12321, kann in PHP und R als Zahl interpretiert werden. Wandle sie zuerst in eine Zeichenfolge um.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Valid Palindrome?

Beide Ansätze laufen in O(n)-Zeit, da jedes Zeichen eine konstante Anzahl von Malen betrachtet wird. Das vorherige Bereinigen benötigt für die Kopie zusätzlichen Speicherplatz von O(n). Die Version mit zwei Zeigern benötigt zusätzlichen Speicherplatz von O(1), da sie nur zwei Indizes speichert.

Wie prüfst du, ob etwas ein Palindrom ist, wenn du nicht alphanumerische Zeichen ignorierst?

Behalte an jedem Ende der Zeichenfolge einen Zeiger. Bewege einen Zeiger über jedes Zeichen hinweg, das kein Buchstabe und keine Ziffer ist. Wenn beide auf Buchstaben oder Ziffern zeigen, vergleiche sie in Kleinbuchstaben. Wenn jedes verglichene Paar übereinstimmt, bis sich die Zeiger treffen, ist die Zeichenfolge ein Palindrom.

Ist eine leere Zeichenfolge ein Palindrom?

Ein leerer Text ist in beiden Richtungen gleich, daher gibt eine Zeichenfolge wie ?!-_, deren Zeichen alle ignoriert werden, true zurück. Beide Ansätze erreichen dies ohne zusätzlichen Code: Der bereinigte Text entspricht seiner umgekehrten Version, und die beiden Zeiger finden nie ein Paar, das sich unterscheidet.

Warum zwei Zeiger verwenden, anstatt die Zeichenkette umzukehren?

Das Umkehren erfordert eine bereinigte Kopie und eine umgekehrte Kopie, was O(n) zusätzlichen Speicherplatz benötigt. Zwei Zeiger vergleichen dieselben Paare direkt und können beim ersten Unterschied anhalten, oft schon nach wenigen Schritten. Interviewer fragen als Folgefrage meist nach dieser Variante.

Python

def isPalindrome(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "Was_it_a_car_or_a_cat_I_saw?"

Erwartet

true