Codewars Lösung | Valid Parentheses

Daniel Kaser|7. Dezember 2023

Lesedauer: ca. 2 min.

Inhalt

Die Fakten
Beschreibung
Lösung
1. Pseudo-Code
2. Code
Feedback

Die Fakten:


Plattform:	codewars.com
Name:	Valid Parentheses
Level:	7 kyu
Sprache:	TypeScript

Beschreibung:

Write a function that takes a string of parentheses, and determines if the order of the parentheses is valid. The function should return true if the string is valid, and false if it's invalid.

Examples

"()"              =&gt;  true
")(()))"          =&gt;  false
"("               =&gt;  false
"(())((()())())"  =&gt;  true

Constraints

0 <= length of input <= 100

All inputs will be strings, consisting only of characters ( and ).
Empty strings are considered balanced (and therefore valid), and will be tested.
For languages with mutable strings, the inputs should not be mutated.

Protip: If you are trying to figure out why a string of parentheses is invalid, paste the parentheses into the code editor, and let the code highlighting show you!

Quelle: codewars.com

Lösung

Pseudo-Code

Wie immer gibt's reichlich Varianten, hier ist eine meiner.

Erst die Lösungsschritte in Pseudo-Code. Los geht’s:

Lösungsschritte

Schritt 1

Wir loopen durch den Input-String.

Schritt 2

Für jede öffnende Klammer erhöhen wir einen Counter um 1.

Schritt 3

Für jede schließende Klammer ziehen wir 1 vom Counter ab.

Schritt 4

Optional: Sollte zu irgendeinem Zeitpunkt der Counter negativ werden, können wir den Loop vorzeitig abbrechen und false zurückgeben.

Schritt 5

Ansonsten geben wir nach dem Loop zurück, ob der Counter 0 ist.

Code

Geil. Übersetzen wir unseren Pseudo-Code in TypeScript:

Lösungsschritte

Meine erste Zeile:

export function validParentheses(str: string): boolean {

Counter initialisieren:

let numOpenParentheses = 0;

Loop durch den Input-String:

  for (const char of str) {

Wenn das aktuelle Zeichen eine öffnende Klammer ist, addieren wir 1 zum Counter:

if (char === "(") numOpenParentheses++;

Wenn das aktuelle Zeichen eine schließende Klammer ist, ziehen wir 1 vom Counter ab:

if (char === ")") numOpenParentheses--;

Optional: Sollte der Counter irgendwann kleiner 0 werden (also mehr schließende als öffnende Klammern), können wir die Funktion vorzeitig beenden:

    if (numOpenParentheses < 0) return false;
  }

Nach dem Loop geben wir aus, ob der Counter 0 ist, also alle öffnenden Klammern geschlossen wurden:

  return numOpenParentheses === 0;
}

Voilá! 💪

Fragen?

Komplettlösung

export function validParentheses(str: string): boolean {
  let numOpenParentheses = 0;

  for (let char of str) {
    if (char === "(") numOpenParentheses++;
    if (char === ")") numOpenParentheses--;

    if (numOpenParentheses < 0) return false;
  }

  return numOpenParentheses === 0;
}

Feedback

Schreib mir!