Typescript Coding Chronicles: Wörter in einer Zeichenfolge umkehren

Problemstellung:

Kehren Sie bei einer gegebenen Eingabezeichenfolge s die Reihenfolge der Wörter um. Ein Wort ist als eine Folge von Nicht-Leerzeichen definiert. Die Wörter in s werden durch mindestens ein Leerzeichen getrennt. Gibt eine Zeichenfolge der Wörter in umgekehrter Reihenfolge zurück, verkettet durch ein einzelnes Leerzeichen.

Beachten Sie, dass s führende oder nachgestellte Leerzeichen oder mehrere Leerzeichen zwischen zwei Wörtern enthalten können. Die zurückgegebene Zeichenfolge sollte nur ein einziges Leerzeichen zwischen den Wörtern enthalten. Fügen Sie keine zusätzlichen Leerzeichen ein.

Beispiel 1:

• Eingabe: s = „Der Himmel ist blau“
• Ausgabe: „Blau ist Himmel“

Beispiel 2:

• Eingabe: s = „Hallo Welt“
• Ausgabe: „Hallo Welt“
• Erklärung: Ihre umgekehrte Zeichenfolge sollte keine führenden oder nachgestellten Leerzeichen enthalten.

Beispiel 3:

• Eingabe: s = „ein gutes Beispiel“
• Ausgabe: „Beispiel gut a“
• Erklärung: Sie müssen mehrere Leerzeichen zwischen zwei Wörtern auf ein einziges Leerzeichen in der umgekehrten Zeichenfolge reduzieren.

Einschränkungen:

• 1 <= s.length <= 10^4
• s enthält englische Buchstaben (Groß- und Kleinbuchstaben), Ziffern und Leerzeichen ''.
• Es gibt mindestens ein Wort in s.

Erster Denkprozess:

Um dieses Problem zu lösen, müssen wir:

1. Teilen Sie die Zeichenfolge in Wörter auf.
2. Kehren Sie die Reihenfolge der Wörter um.
3. Fügen Sie die Wörter wieder zusammen, mit jeweils einem Leerzeichen dazwischen.

Grundlegende Lösung:

Code:

function reverseWordsBruteForce(s: string): string {
    // Split the string by spaces and filter out empty strings
    let words = s.trim().split(/\s+/);

    // Reverse the array of words
    words.reverse();

    // Join the words with a single space
    return words.join(' ');
}

Zeitkomplexitätsanalyse:

• Zeitkomplexität: O(n), wobei n die Länge der Zeichenfolge ist. Das Teilen, Umkehren und Zusammenfügen nimmt lineare Zeit in Anspruch.
• Raumkomplexität: O(n), wobei n die Länge der Zeichenfolge ist. Wir speichern die Wörter in einem Array und das Endergebnis in einem String.

Einschränkungen:

Diese Lösung ist angesichts der Einschränkungen effizient. Allerdings wird zusätzlicher Platz für die Wortreihe benötigt.

Optimierte Lösung:

Wenn der Zeichenfolgendatentyp veränderbar ist und wir ihn direkt mit O(1) zusätzlichem Leerzeichen lösen müssen, können wir eine Zwei-Zeiger-Technik verwenden, um die Wörter innerhalb der ursprünglichen Zeichenfolge umzukehren.

Code:

function reverseWordsOptimized(s: string): string {
    // Trim the string and convert it to an array of characters
    let chars = s.trim().split('');

    // Helper function to reverse a portion of the array in place
    function reverse(arr: string[], left: number, right: number) {
        while (left < right) {
            [arr[left], arr[right]] = [arr[right], arr[left]];
            left++;
            right--;
        }
    }

    // Reverse the entire array of characters
    reverse(chars, 0, chars.length - 1);

    // Reverse each word in the reversed array
    let start = 0;
    for (let end = 0; end <= chars.length; end++) {
        if (end === chars.length || chars[end] === ' ') {
            reverse(chars, start, end - 1);
            start = end + 1;
        }
    }

    // Join the characters back into a string and split by spaces to remove extra spaces
    return chars.join('').split(/\s+/).join(' ');
}

Zeitkomplexitätsanalyse:

• Zeitkomplexität: O(n), wobei n die Länge der Zeichenfolge ist. Jedes Zeichen wird konstant oft verarbeitet.
• Platzkomplexität: O(1), da wir das Array an Ort und Stelle ändern und nur eine konstante Menge an zusätzlichem Platz verwenden.

Verbesserungen gegenüber der Basislösung:

• Die optimierte Lösung reduziert die Platzkomplexität, indem sie direkte Vorgänge für das Zeichenarray durchführt.

Randfälle und Tests:

Randfälle:

1. Die Zeichenfolge enthält führende und nachgestellte Leerzeichen.
2. Die Zeichenfolge enthält mehrere Leerzeichen zwischen Wörtern.
3. Die Zeichenfolge enthält nur ein Wort.
4. Die Zeichenfolgenlänge liegt am minimalen oder maximalen Grenzwert.

Testfälle:

console.log(reverseWordsBruteForce("the sky is blue")); // "blue is sky the"
console.log(reverseWordsBruteForce("  hello world  ")); // "world hello"
console.log(reverseWordsBruteForce("a good   example")); // "example good a"
console.log(reverseWordsBruteForce("singleWord")); // "singleWord"
console.log(reverseWordsBruteForce("   ")); // ""

console.log(reverseWordsOptimized("the sky is blue")); // "blue is sky the"
console.log(reverseWordsOptimized("  hello world  ")); // "world hello"
console.log(reverseWordsOptimized("a good   example")); // "example good a"
console.log(reverseWordsOptimized("singleWord")); // "singleWord"
console.log(reverseWordsOptimized("   ")); // ""

Allgemeine Problemlösungsstrategien:

1. Verstehen Sie das Problem:Lesen Sie die Problemstellung sorgfältig durch, um die Anforderungen und Einschränkungen zu verstehen.
2. Schlüsseloperationen identifizieren: Bestimmen Sie die erforderlichen Schlüsseloperationen, z. B. Teilen, Umkehren und Verbinden von Wörtern.
3. Für Lesbarkeit optimieren:Verwenden Sie eine klare und prägnante Logik, um sicherzustellen, dass der Code leicht zu befolgen ist.
4. Gründlich testen:Testen Sie die Lösung mit verschiedenen Fällen, einschließlich Randfällen, um die Richtigkeit sicherzustellen.

Identifizieren ähnlicher Probleme:

1. String-Manipulation:

   • Probleme, bei denen Sie Zeichenfolgen basierend auf bestimmten Bedingungen ändern müssen.
   • Beispiel: Umkehren der Reihenfolge der Zeichen in jedem Wort eines Satzes.

2. Zwei-Zeiger-Technik:

   • Probleme, bei denen die Verwendung von zwei Zeigern zur Optimierung der Lösung beitragen kann.
   • Beispiel: Duplikate aus einem sortierten Array entfernen.

3. In-Place-Algorithmen:

   • Probleme, bei denen Vorgänge vor Ort mit begrenztem zusätzlichem Platz durchgeführt werden müssen.
   • Beispiel: Drehen eines Arrays um k Schritte nach rechts.

Abschluss:

• Das Problem der Umkehrung von Wörtern in einer Zeichenfolge kann sowohl mit einem Brute-Force-Ansatz als auch mit einem optimierten In-Place-Ansatz effizient gelöst werden.
• Es ist entscheidend, das Problem zu verstehen und es in überschaubare Teile zu zerlegen.
• Die Verwendung klarer Logik und die Optimierung der Lesbarkeit stellen sicher, dass die Lösung leicht zu befolgen ist.
• Tests mit verschiedenen Randfällen stellen die Robustheit sicher.
• Das Erkennen von Mustern in Problemen kann dabei helfen, ähnliche Lösungen auf andere Herausforderungen anzuwenden.

Durch das Üben solcher Probleme und Strategien können Sie Ihre Problemlösungsfähigkeiten verbessern und besser auf verschiedene Programmierherausforderungen vorbereitet sein.

Das obige ist der detaillierte Inhalt vonTypescript Coding Chronicles: Wörter in einer Zeichenfolge umkehren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!