Palindrome String

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

Vergleiche das erste Zeichen mit dem letzten, das zweite mit dem vorletzten und so weiter zur Mitte hin. Wenn sich ein beliebiges Paar unterscheidet, ist die Zeichenfolge kein Palindrom. Zwei Indizes, die an beiden Enden beginnen und sich nach innen bewegen, erledigen das in einem Durchlauf.

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

Ja. Die Zwei-Zeiger-Prüfung liest die Zeichen direkt und speichert zwei Indizes, sodass sie O(1) zusätzlichen Speicherplatz benötigt. s mit seiner Umkehrung zu vergleichen, ist kürzer zu schreiben, erzeugt aber eine zweite Zeichenkette mit n Zeichen.

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

O(n) für eine Zeichenkette der Länge n . Die Prüfung mit zwei Zeigern führt höchstens n / 2 Vergleiche durch und stoppt beim ersten Unterschied, daher benötigt coddy einen Vergleich.

Q: Ist ein einzelnes Zeichen ein Palindrom?

Ja, es liest sich in beiden Richtungen gleich. In der Schleife mit zwei Zeigern starten left und right beide am 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 sich von links nach rechts genauso liest wie von rechts nach links, wie level. Schreibe eine Funktion, die eine Zeichenfolge s aus englischen Kleinbuchstaben erhält und true zurückgibt, wenn s ein Palindrom ist, und andernfalls false.

Funktion

isPalindrome(s: string) → boolean

sstring: die Zeichenfolge in Kleinbuchstaben, die überprüft werden soll
Gibt zurückboolean: wahr, wenn s in beiden Richtungen gleich gelesen wird

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, daher 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.

Weiterführende Frage

Wie würdest du die beiden Zeiger so ändern, dass sie Leerzeichen und Satzzeichen überspringen und Groß- und Kleinschreibung ignorieren, sodass Was it a car or a cat I saw als Palindrom gilt?

Tipps

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

0 von 3 geöffnet

Lösung

Ein Palindrom ist gleich seiner Umkehrung. Daher kannst du die Umkehrung erstellen und vergleichen. Die Kopie brauchst du nicht: Das erste Zeichen muss mit dem letzten übereinstimmen, das zweite mit dem vorletzten und so weiter. Zwei Indizes, die sich nach innen bewegen, prüfen diese Paare direkt und stoppen beim ersten Unterschied.

Vergleiche die Zeichenfolge mit ihrer Umkehrung

Idee

Drehe s um und vergleiche: Umgedreht ergibt racecar wieder racecar, und umgedreht ergibt coddy yddoc. Eine Zeichenfolge liest sich genau dann in beide Richtungen gleich, wenn sie ihrem umgedrehten Gegenstück entspricht.

Der Zeitaufwand beträgt O(n), aber die umgedrehte Kopie benötigt zusätzlichen Speicherplatz von O(n) – 50.000 Zeichen bei n = 5 × 10^4. Außerdem wird immer die gesamte Zeichenfolge verarbeitet: Bei coddy lässt sich die Entscheidung bereits anhand des ersten und letzten Buchstabens treffen, dennoch werden zuerst alle fünf Buchstaben umgedreht.

Algorithmus

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

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

Zwei Zeiger von beiden Enden

Idee

Beim Umkehren wird der Index i zum Index n-1-i. Daher ist s genau dann gleich seiner Umkehrung, wenn für jedes i gilt: s[i] ist gleich s[n-1-i]. Jedes Paar kommt in dieser Bedingung zweimal vor, daher genügt es, die linke Hälfte zu überprüfen. In racecar lauten die Paare (0, 6), (1, 5) und (2, 4); das mittlere e an Index 3 benötigt kein Gegenstück.

Das erste abweichende Paar beweist, dass die Antwort false lautet; daher steht das Ergebnis für coddy nach einem Vergleich fest. Es werden höchstens n / 2 Vergleiche durchgeführt, also beträgt die Laufzeit O(n), und zwei Indizes benötigen O(1) Speicherplatz. R liest den String zunächst 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 sich unterscheiden, 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, hat jedes Paar übereingestimmt: 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

true zurückzugeben, sobald ein Paar übereinstimmt. abca besteht die Prüfung des äußeren Paars, aber nicht die des inneren; true wird also erst nach der Schleife zurückgegeben.
right auf n statt auf n-1 zu setzen, wodurch über das Ende hinaus gelesen wird (in C das abschließende '\0'). In Lua und R beginnen die Indizes bei 1 und laufen bis n, daher wird right dort tatsächlich auf n gesetzt.
Zeichenketten in C mit == zu vergleichen. reversed == s vergleicht zwei Zeiger und ist bei einer Kopie false; verwende strcmp.
Die Umkehrung mit result = result + ch aufzubauen. Bei jedem Schritt wird die bisherige Zeichenkette kopiert: etwa 1.25 × 10^9 Zeichenkopien bei 50,000 Buchstaben.
Eine Swift-Zeichenkette mit einer Ganzzahl zu indizieren: Das lässt sich nicht kompilieren. Durchlaufe s.utf8 oder kopiere die Zeichen in ein Array.

Häufige Fragen4

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

Vergleiche das erste Zeichen mit dem letzten, das zweite mit dem vorletzten und so weiter zur Mitte hin. Wenn sich ein beliebiges Paar unterscheidet, ist die Zeichenfolge kein Palindrom. Zwei Indizes, die an beiden Enden beginnen und sich nach innen bewegen, erledigen das in einem Durchlauf.

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

Ja. Die Zwei-Zeiger-Prüfung liest die Zeichen direkt und speichert zwei Indizes, sodass sie O(1) zusätzlichen Speicherplatz benötigt. s mit seiner Umkehrung zu vergleichen, ist kürzer zu schreiben, erzeugt aber eine zweite Zeichenkette mit n Zeichen.

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

O(n) für eine Zeichenkette der Länge n. Die Prüfung mit zwei Zeigern führt höchstens n / 2 Vergleiche durch und stoppt beim ersten Unterschied, daher benötigt coddy einen Vergleich.

Ist ein einzelnes Zeichen ein Palindrom?

Ja, es liest sich in beiden Richtungen gleich. In der Schleife mit zwei Zeigern starten left und right beide am Index 0, die Schleife wird nie ausgeführt und die Funktion gibt true zurück.

def isPalindrome(s):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

s = "racecar"

Erwartete Ausgabe

true