Eine andere Möglichkeit, Palindrome zu überprüfen

Mittlerweile habe ich in LinkedIn und Twitter gescrollt und bin auf eine sehr häufige Codierungsherausforderung gestoßen: Überprüfen Sie, ob eine Zeichenfolge ein Palindrom ist.

Es ist eine sehr einfache Herausforderung. Ein Palindrom ist ein Wort oder eine Phrase, die in- und rückwärts gleich gelesen werden kann. Genau wie:

• tesset
• Mama
• biaib

und so weiter.

Aber der allgemeine Ansatz, den die Leute verfolgen, ist dieser:

Mit anderen Worten, sie nehmen die ursprüngliche Zeichenfolge, kehren sie um und vergleichen sie dann mit dem Original.
Es ist ein sehr gültiger Ansatz, aber ich möchte einen cleveren Ansatz dafür vorschlagen.

Stellen Sie sicher, dass Sie eine neue Zuordnung für die Zeichenfolge erstellen müssen, und vergleichen Sie dann Zeichen für Zeichen. Die größere Herausforderung besteht darin, wie man es mit einem O(1) mehr Speicher und weniger Vergleichen macht?

Lassen Sie mich das besser erklären.

Der bessere Ansatz zur Lösung dieses Problems ist die Verwendung eines Zwei-Punkte-Ansatzes.

Ein String ist nichts anderes als ein char-Array, und wir können ihn char für char durchgehen und Durchläufe und Vergleiche mit jedem char des Arrays durchführen.

Lassen Sie es uns mit dem neuen Ansatz mit zwei Zeigern umgestalten.
Das erste, was wir machen müssen, ist, ein Runenstück daraus zu nehmen:

  r := []rune(str);

Strings in Go sind schreibgeschützt, daher ist der String grundsätzlich unveränderlich und kann nicht geändert werden. Ansonsten kann das Runen-Slice geändert werden, und dann wird durch die Konvertierung zwischen den beiden eine Kopie der String-Bytes erstellt, aber dann erstellen wir hier keine weitere Kopie, da wir im selben Stapelrahmen fortfahren, und das tun wir nicht Ich werde eine neue Saite produzieren.

Danach beginnen wir die Schleife mit einem Zeiger am Anfang der Rune und einem anderen am Ende und durchlaufen sie, bis einer den anderen kreuzt. Wir werden die Vergleiche hier durchführen:

func isPalindrome(str string) bool {
    r := []rune(str)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        if r[i] != r[j] {
            return false
        }
    }
    return true
}

Wenn also die Vergleiche in Ordnung sind und alle Zeichen gleich sind, handelt es sich um ein Palindrom. Andernfalls wird sofort false zurückgegeben.

Das obige ist der detaillierte Inhalt vonEine andere Möglichkeit, Palindrome zu überprüfen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!