Palindrome String

Q: Wie prüfst du, ob eine Zeichenkette ein Palindrom ist?

Vergleiche das erste Zeichen mit dem letzten, das zweite mit dem vorletzten und so weiter zur Mitte hin. Wenn sich ein Paar unterscheidet, ist die Zeichenfolge kein Palindrom; stimmen alle Paare überein, ist sie eines. Zwei Indizes, die an beiden Enden beginnen und sich nach innen bewegen, erledigen dies in einem Durchgang.

Q: Kannst du ein Palindrom ohne zusätzlichen Speicherplatz überprüfen?

Ja. Die Prüfung mit zwei Zeigern liest die Zeichen direkt an ihrer Position und speichert nur zwei Indizes, daher benötigt sie O(1) zusätzlichen Speicherplatz. s mit seiner Umkehrung zu vergleichen, ist kürzer zu schreiben, erstellt aber eine zweite Zeichenkette mit n Zeichen.

Q: Wie hoch ist die Zeitkomplexität beim Prüfen, ob eine Zeichenkette ein Palindrom ist?

Für eine Zeichenfolge der Länge n beträgt die Komplexität O(n) . Die Prüfung mit zwei Zeigern führt höchstens n / 2 Vergleiche durch und endet beim ersten Unterschied. Eine Zeichenfolge, deren erstes und letztes Zeichen unterschiedlich sind, wird daher nach einem Vergleich beurteilt.

Q: Ist ein einzelnes Zeichen ein Palindrom?

Ja. Ein Zeichen liest sich in beide Richtungen gleich, daher lautet die Antwort true . In der Zwei-Zeiger-Schleife beginnen left und right beide bei Index 0, die Schleife wird nie ausgeführt und die Funktion gibt true zurück.

EinsteigerZwei Zeiger Arrays und Strings

+10

Eine Zeichenfolge ist ein Palindrom, wenn sie von links nach rechts genauso gelesen wird wie von rechts nach links, wie level. Schreibe eine Funktion, die eine Zeichenfolge s aus englischen Kleinbuchstaben entgegennimmt und true zurückgibt, wenn s ein Palindrom ist, und andernfalls false.

Funktion

isPalindrome(s: string) → boolean

sstring: die zu überprüfende Zeichenfolge in Kleinbuchstaben
Gibt zurückboolean: wahr, wenn sich s in beide Richtungen gleich liest

Einschränkungen

1 ≤ s.length ≤ 5 × 10⁴
s enthält nur englische Kleinbuchstaben (a bis z).

Beispiele

Eingabe: s = "racecar"
Ausgabe: true
Erklärung: Vergleiche von außen nach innen: r mit r, a mit a, c mit c. Das mittlere e hat kein Gegenstück und braucht auch keines, also lautet die Antwort true.

Eingabe: s = "abba"
Ausgabe: true
Erklärung: Bei einer geraden Länge hat jeder Buchstabe einen Partner: Die beiden as passen zusammen und die beiden bs passen zusammen, also lautet die Antwort true.

Eingabe: s = "coddy"
Ausgabe: false
Erklärung: Der erste Buchstabe c und der letzte Buchstabe y unterscheiden sich bereits, daher ist coddy kein Palindrom und die Antwort lautet false.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Ein Satz wie Was it a car or a cat I saw ist ein Palindrom, wenn man Groß- und Kleinschreibung, Leerzeichen und Satzzeichen ignoriert. Wie würdest du die beiden Zeiger ändern, damit sie diese Zeichen überspringen?

Tipps

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

0 von 3 geöffnet

Lösung

Ein Palindrom ist gleich seiner Umkehrung, daher erstellt die direkte Prüfung die Umkehrung und vergleicht beide. Die bessere Prüfung erstellt nichts: Das erste Zeichen muss mit dem letzten übereinstimmen, das zweite mit dem vorletzten und so weiter bis zur Mitte. Zwei Indizes, die nach innen wandern, prüfen diese Zeichenpaare direkt und brechen beim ersten Unterschied ab.

Vergleiche die Zeichenfolge mit ihrer Umkehrung

Idee

s in beiden Richtungen zu lesen bedeutet, dass s seinem Umkehrstring entspricht. Kehre ihn also um und vergleiche: Umgekehrt ergibt racecar racecar, und umgekehrt ergibt coddy yddoc, was nicht übereinstimmt.

Beim Erstellen des Umkehrstrings und beim Vergleichen wird jedes Zeichen einmal verarbeitet, daher beträgt die Laufzeit O(n). Die umgekehrte Kopie enthält n weitere Zeichen, was O(n) zusätzlichen Speicherplatz bedeutet: Bei n = 5 × 10^4 sind das 50.000 Zeichen, die nur zum Vergleichen erstellt und anschließend verworfen werden.

Außerdem wird jedes Mal die gesamte Arbeit ausgeführt. Bei coddy lässt sich die Entscheidung anhand des ersten und letzten Buchstabens treffen, doch dieser Ansatz kehrt alle fünf Buchstaben um, bevor er sie vergleicht.

Algorithmus

Erstelle die Umkehrung von s mit der Umkehrfunktion der Sprache oder einer Schleife vom letzten bis zum ersten Zeichen.
Vergleiche die Umkehrung mit s.
Gib true zurück, wenn sie gleich sind, und andernfalls false.

def isPalindrome(s):
    return s == s[::-1]

Zwei Zeiger von beiden Enden

Idee

Beim Umkehren wird das Zeichen am Index i an den Index n-1-i verschoben. Daher ist s genau dann gleich seiner Umkehrung, wenn s[i] für jedes i gleich s[n-1-i] ist. Jedes Paar kommt in dieser Liste zweimal vor, also musst du nur die linke Hälfte überprüfen. Setze left auf Index 0 und right auf Index n-1, vergleiche die beiden Zeichen und bewege beide Zeiger jeweils einen Schritt nach innen.

Halte an, wenn sich die Zeiger treffen oder überkreuzen. Bei racecar überprüfen sie die Indexpaarungen (0, 6), (1, 5) und (2, 4) und treffen sich dann bei Index 3, dem mittleren e, das keinen Partner braucht. Bei abba überprüfen sie (0, 3) und (1, 2) und überkreuzen sich dann. Das erste abweichende Paar beweist, dass die Antwort false ist; du gibst also sofort zurück: Bei coddy steht das Ergebnis nach einem Vergleich fest.

Es finden höchstens n / 2 Vergleiche statt, also beträgt die Laufzeit O(n). Der einzige Speicherbedarf sind zwei Indizes, also O(1) Speicherplatz. R ist die Ausnahme: Zuerst liest es die Zeichenfolge als Vektor von Zeichencodes ein, was O(n) kostet.

Algorithmus

Setze left = 0 und right = n-1.
Vergleiche s[left] mit s[right], solange left < right gilt.
Wenn sie unterschiedlich sind, gib false zurück.
Andernfalls erhöhe left um 1, verringere right um 1 und wiederhole den Vorgang.
Wenn sich die Zeiger treffen oder überkreuzen, stimmt jedes Paar überein: Gib true zurück.

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

Stolperfallen und Grenzfälle

Die Schleife ist kurz, daher stecken die Fehler in ihren Grenzen und ihren Rückgabeanweisungen.

true zurückgeben, sobald ein Paar übereinstimmt. abca besteht die Prüfung des äußeren Paars und scheitert beim inneren, daher darf true erst nach dem Ende der Schleife zurückgegeben werden.
right auf n statt auf n-1 setzen, wodurch über das Ende hinaus gelesen wird (in C das abschließende '\0'). In Lua und R laufen die Indizes von 1 bis n, daher beginnt right dort bei n.
Strings anhand ihrer Adresse vergleichen. In C vergleicht reversed == s zwei Zeiger und ist bei einer neu erstellten Kopie immer falsch; verwende strcmp.
Die Umkehrung in einer Schleife mit result = result + ch erstellen. Bei jedem Schritt wird der gesamte bisherige String kopiert, bei 50,000 Buchstaben etwa 1.25 × 10^9 Zeichenkopien.
Einen Swift-String mit einer Ganzzahl indizieren. Das lässt sich nicht kompilieren; durchlaufe s.utf8 mit dessen eigenen Indizes oder kopiere die Zeichen in ein Array.

Häufige Fragen4

Wie prüfst du, ob eine Zeichenkette ein Palindrom ist?

Vergleiche das erste Zeichen mit dem letzten, das zweite mit dem vorletzten und so weiter zur Mitte hin. Wenn sich ein Paar unterscheidet, ist die Zeichenfolge kein Palindrom; stimmen alle Paare überein, ist sie eines. Zwei Indizes, die an beiden Enden beginnen und sich nach innen bewegen, erledigen dies in einem Durchgang.

Kannst du ein Palindrom ohne zusätzlichen Speicherplatz überprüfen?

Ja. Die Prüfung mit zwei Zeigern liest die Zeichen direkt an ihrer Position und speichert nur zwei Indizes, daher benötigt sie O(1) zusätzlichen Speicherplatz. s mit seiner Umkehrung zu vergleichen, ist kürzer zu schreiben, erstellt aber eine zweite Zeichenkette mit n Zeichen.

Wie hoch ist die Zeitkomplexität beim Prüfen, ob eine Zeichenkette ein Palindrom ist?

Für eine Zeichenfolge der Länge n beträgt die Komplexität O(n). Die Prüfung mit zwei Zeigern führt höchstens n / 2 Vergleiche durch und endet beim ersten Unterschied. Eine Zeichenfolge, deren erstes und letztes Zeichen unterschiedlich sind, wird daher nach einem Vergleich beurteilt.

Ist ein einzelnes Zeichen ein Palindrom?

Ja. Ein Zeichen liest sich in beide Richtungen gleich, daher lautet die Antwort true. In der Zwei-Zeiger-Schleife beginnen left und right beide bei Index 0, die Schleife wird nie ausgeführt und die Funktion gibt true zurück.

Python

def isPalindrome(s):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

s = "racecar"

Erwartet

true