Leetcode: Gültige Klammern

4394
Gilad

https://leetcode.com/problems/valid-parentheses/

Bei einer Zeichenfolge enthält nur die Zeichen (, ), {, }, [ und ], festzustellen, ob die eingegebene Zeichenkette gültig ist.

Damit eine Eingabezeichenfolge gültig ist:

  • Offene Klammern müssen durch die gleiche Art von Klammern geschlossen werden.
  • Offene Klammern müssen in der richtigen Reihenfolge geschlossen werden.

Beachten Sie, dass eine leere Zeichenfolge als gültig betrachtet wird.

Beispiel 1:

Eingabe: ()
Ausgabe: wahr

Beispiel 2

Eingabe: ()[]{}
Ausgabe: wahr

Beispiel 3:

Eingabe: (]
Ausgabe: falsch

Beispiel 4:

Eingabe: ([)]
Ausgabe: falsch

Beispiel 5

Eingabe: {[]}
Ausgabe: wahr

using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace StackQuestions
{
    [TestClass]
    public class ValidParentheses
    {
        [TestMethod]
        public void OpenOpenClosedClosedMixTest()
        {
            string input = "([)]";
            bool result = IsValid(input);
            Assert.IsFalse(result);
        }
        [TestMethod]
        public void OnePairTest()
        {
            string input = "()";
            bool result = IsValid(input);
            Assert.IsTrue(result);
        }

        public bool IsValid(string s)
        {
            Stack<char> myStack = new Stack<char>();
            foreach (var curr in s)
            {
                if (curr == '(')
                {
                    myStack.Push(curr);
                }
                else if (curr == '[')
                {
                    myStack.Push(curr);
                }
                else if (curr == '{')
                {
                    myStack.Push(curr);
                }
                else if (curr == ')')
                {
                    if (myStack.Count > 0)
                    {
                        var top = myStack.Pop();
                        if (top != '(')
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
                else if (curr == ']')
                {
                    if (myStack.Count > 0)
                    {
                        var top = myStack.Pop();
                        if (top != '[')
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }
                else if (curr == '}')
                {
                    if (myStack.Count > 0)
                    {
                        var top = myStack.Pop();
                        if (top != '{')
                        {
                            return false;
                        }
                    }
                    else
                    {
                        return false;
                    }
                }

            }
            return myStack.Count == 0;
        }

    }
}

Bitte überprüfen Sie den Kodierungsstil, da es sich um ein Bewerbungsgespräch mit einer 30-minütigen Kodierung handelt.

Antworten
21
Sollte `IsValidReview (") ("));` wahr sein? aloisdg vor einem Jahr 0

3 Antworten auf die Frage

44
Henrik Hansen

Sie haben die Arbeit in 30 Minuten erledigt und die Verwendung eines Stapels ist der Weg, also ist dies ein guter Anfang. Meiner Meinung nach schreiben Sie etwas zu viel (sich wiederholender) Code. Wenn Sie switchstattdessen eine -statement verwenden, könnte es viel einfacher zu lesen sein :

public bool IsValidReview(string s)
{
  Stack<char> endings = new Stack<char>();

  foreach (var curr in s)
  {
    switch (curr)
    {
      case '(':
        endings.Push(')');
        break;
      case '[':
        endings.Push(']');
        break;
      case '{':
        endings.Push('}');
        break;
      case ')':
      case ']':
      case '}':
        if (endings.Count == 0 || endings.Pop() != curr)
          return false;
        break;

    }
  }

  return endings.Count == 0;
}

Hier wird die entsprechende abschließende Klammer in den Stapel anstatt in die Startposition geschoben, wodurch die Überprüfung erleichtert wird, wenn das Ende angezeigt wird.

Der Name myStacksagt nicht viel aus, daher habe ich ihn im Kontext etwas sinnvolleres geändert.

Cool, danke, ich habe mich gefragt, ob das Switch-Case der richtige Weg ist oder nicht Gilad vor einem Jahr 1
@ Gilad Ich denke, ein Wörterbuch würde gut passen. [Überprüfen Sie auch meine Antwort] (https://codereview.stackexchange.com/a/212466/35439). aloisdg vor einem Jahr 1
Da die Eingabe nur aus Klammern besteht, können die letzten 3 Fälle durch "default" ersetzt werden, es sei denn, Sie möchten auch mit anderen Zeichen umgehen. In diesem Fall sollte am Ende ein "default" stehen. Voile vor einem Jahr 0
@Henrik Hansen Code Review verdoppelte gerade Ihre Antwort auf meine Frage, deshalb bekommen wir so viele gute 1er-Jobs! Gilad vor einem Jahr 1
@Voile Ich würde argumentieren, dass Sie `default` nicht verwenden, um die letzten drei Fälle abzudecken. "default" sollte in einer Situation verwendet werden, in der eine Eingabe nicht mit den erwarteten Fällen übereinstimmt, und ich würde es vorziehen, wenn sie ohnehin als getrennte Fälle behandelt werden, um die Absicht des Codes klarer zu machen. Ich stimme zu, dass es jedoch eine generelle "Standardeinstellung" für die ungültige Eingabebehandlung geben sollte. Abion47 vor einem Jahr 3
Das ist schöner Code. Ich glaube nicht, dass ich das unter dem Druck eines Bewerbungsgesprächs je hätte. solarflare vor einem Jahr 0
@solarflare muss in dieser Ebene nicht geschrieben werden. Mein Code hat dieses Interview bestanden. Ziel ist es, sich selbst zu verbessern. Wie Sie sehen, gibt es dafür immer einen Raum. Gilad vor einem Jahr 2
Ich würde "default" verwenden, um abschließende Parens zu fangen, da die Zeichenfolgen nur paren sind somebody vor einem Jahr 0
15
aloisdg

Dies ist eine Fortsetzung von @Henrik Hansen. Anstelle eines Schalters würde ich eine verwenden Dictionary<T, K>. Ein Wörterbuch bietet zwei Hauptvorteile: eine bessere Lesbarkeit und die Unterdrückung jeder magischen Zeichenkette von Ihrer Funktion.

public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
    {'(', ')'},
    {'[', ']'},
    {'{', '}'}
};

public static bool IsValidReview(string input)
{
    var endings = new Stack<char>();
    foreach (var current in input)
    {
        if (brackets.ContainsKey(current))
        {
            endings.Push(brackets[current]);
        }
        else if (endings.Count == 0 || endings.Pop() != current)
        {
            return false;
        }
    }
    return endings.Count == 0;
}

Probieren Sie es online aus!

Zum Hinzufügen können Sie stattdessen auch ein Tuple-Array verwenden. var (öffnend, schließend) = ('(', ')') `sollte heutzutage gültige Syntax sein. Dadurch können Sie mehrere Schließungen für eine Öffnung haben oder umgekehrt. Sie können auch die begrenzte Zerstörungsfunktion von C # verwenden, um sie ein bisschen ergonomischer zu gestalten. user29920 vor einem Jahr 0
Ich stimme nicht zu, dass die Verwendung eines `Dictionary` die Lesbarkeit verbessert. Es ist ein bisschen schwierig zu sagen, was dieser Code tun soll, vor allem wenn ich den Zweck nicht bereits kannte, während @ HenrikHansens Antwort sehr klar und präzise ist. Die "Unterdrückung der magischen Saiten" ist ein fairer Punkt, obwohl in diesem speziellen Fall die Verwendung der magischen Saiten (oder vielmehr der Zeichen) begrenzt und klar genug ist, so dass es mir nicht unbedingt wichtig wäre, wenn ich sie im Produktionscode sehen würde. Abion47 vor einem Jahr 1
Sicher, die `switch`-Lösung hat magische Strings, aber sie ist 1. schneller / performanter (1 Objekt weniger) und 2. lesbarer somebody vor einem Jahr 1
Tatsächlich sind technisch magische Saiten sehr selten ... dies sind keine magischen Saiten. Der Grund, warum sie das sind, was sie sind, ist sehr klar. Magische Zahlen sind dagegen sehr verbreitet somebody vor einem Jahr 1
@aloisdg Ihre Lösung hat eine Zeitkomplexität von "O (n ^ 2)", die andere Lösung hat eine Zeitkomplexität von "O (n)". Mit einem Mehrtastenwörterbuch können Sie eine bessere zeitliche Komplexität erreichen Node.JS vor einem Jahr 0
Dies erzeugt keine korrekte Ausgabe. Zum Beispiel, wenn die Zeichenfolge andere Zeichen als die geschweiften Klammern enthält. Zum Beispiel: `" 5 "` oder `" (5) "`. Dies kann behoben werden, indem die Anweisung `brackets.Values.Any ()` entfernt wird (nicht sicher, was es tut, dass `endings.Pop ()! = Current` noch nicht funktioniert). [Geige] (https://dotnetfiddle.net/oJqrYT) JAD vor einem Jahr 0
Ich sehe gerade jetzt, dass die Eingabezeichenfolge nur diese Klammern enthält. Das bedeutet, dass es nicht notwendig ist, über 'Klammern.Werte' zu laufen. JAD vor einem Jahr 0
10
VisualMelon

Ein paar kleine Dinge hinzuzufügen:

  • Möglicherweise nicht auf ein zeitlich festgelegtes Interview anwendbar, aber Inline-Dokumentation ( ///) für öffentliche Mitglieder ist immer nett und würde helfen, den ansonsten vagen IsValidMethodennamen zu erklären .

  • Ich möchte eine Ausnahme auslösen, wenn ein anderes Zeichen gefunden wird, da das Verhalten undefiniert und undokumentiert ist. Die Spezifikation besagt, dass nur angenommen ()[]{}wird, dass sie in der Zeichenfolge angezeigt wird. Dies bedeutet, dass jeder Benutzer, der sie falsch verwendet (indem er solche Zeichen einschließt), informiert werden sollte (vielleicht wird davon ausgegangen, dass er <>auch handelt?). Wenn ein Kunde sich auf dieses (undokumentierte) Verhalten verlassen würde, solche Charaktere einfach zu ignorieren, müssten Sie in Zukunft eine weitere "undokumentierte" Funktion (oder einen unglücklichen Kunden) beibehalten.

  • Gibt es einen Grund, warum die Methode nicht ist static? Abgesehen von den konzeptionellen Vorteilen würde das Feststellen der Statik deutlich machen, dass es sich nicht um einen Zustand handelt, und die Verwendung wird einfacher.

  • Das ist eine sehr begrenzte Anzahl von Testfällen: Sie testen {}überhaupt nicht.