22
\$\begingroup\$

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

Given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

For an input string to be valid:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Note that an empty string is considered valid.

Example 1:

Input: ()
Output: true

Example 2:

Input: ()[]{}
Output: true

Example 3:

Input: (]
Output: false

Example 4:

Input: ([)]
Output: false

Example 5:

Input: {[]}
Output: true

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;
        }

    }
}

Please review coding style as it was a job interview with 30 minutes to code.

\$\endgroup\$
  • \$\begingroup\$ Should IsValidReview(")(")); be true? \$\endgroup\$ – aloisdg Jan 29 at 12:58
45
\$\begingroup\$

You get the job done in 30 minutes and the use of a stack is the way to go, so that's a good start. In my opinion you're writing a little too much (repetitive) code and it could be a lot easier to read if you use a switch-statement instead:

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;
}

Here the corresponding ending parenthesis is pushed to the stack instead of the starting one, which makes it easier to check when the ending shows up.

The name myStack doesn't say much, so I have changed it to something more meaningful in the context.

\$\endgroup\$
  • 1
    \$\begingroup\$ Cool thanks I was wondering if switch case is the way to go or not \$\endgroup\$ – Gilad Jan 29 at 10:52
  • 1
    \$\begingroup\$ @Gilad I think a Dictionary would suit well. Check my answer too. \$\endgroup\$ – aloisdg Jan 29 at 12:59
  • 1
    \$\begingroup\$ @Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job! \$\endgroup\$ – Gilad Jan 29 at 20:54
  • 3
    \$\begingroup\$ @Voile I'd argue against using default as a catch-all to cover the last three cases. default should be used in a situation where an input doesn't match any expected cases, and I'd prefer them to be kept as distinct cases anyway to make the intent of the code clearer. I do agree that there should be a general default for invalid input handling, though. \$\endgroup\$ – Abion47 Jan 29 at 23:27
  • 2
    \$\begingroup\$ @solarflare you do not need to write in this level. My code passed this interview. The goal here is to try and improve ourself. As you can see there is a room for that always. \$\endgroup\$ – Gilad Jan 30 at 5:19
16
\$\begingroup\$

This is a follow up of @Henrik Hansen. Instead, of a switch I would use a Dictionary<T, K>. A Dictionary offers two main advantages: an increase readibility and the suppression of every magic string from your function.

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;
}

Try it Online!

\$\endgroup\$
  • \$\begingroup\$ Just to add, you may also use an array of Tuple instead. var (opening, closing) = ('(', ')') should be valid syntax nowadays. This lets you have multiple closings for one opening, or vice versa. It also lets you use C#'s limited destructuring to make it a bit more ergonomic. \$\endgroup\$ – user29920 Jan 29 at 22:25
  • 1
    \$\begingroup\$ I disagree that using a Dictionary offers improved readability. It's a bit difficult to tell what this code is supposed to do, especially if I didn't already know its purpose, whereas @HenrikHansen's answer is very clear and concise. The "magic string suppression" is a fair point, though in this particular case the usage of the magic strings (or, rather, characters) is limited and clear enough that I wouldn't necessarily care if I saw it in production code. \$\endgroup\$ – Abion47 Jan 29 at 23:31
  • 1
    \$\begingroup\$ Sure, the switch solution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable \$\endgroup\$ – somebody Jan 30 at 5:35
  • 1
    \$\begingroup\$ Well actually, technically magic strings are very rare... these are not magic strings. The reason why they are what they are is very clear. Magic numbers, on the other hand, are very common \$\endgroup\$ – somebody Jan 30 at 5:35
  • \$\begingroup\$ @aloisdg your solution has a time complexity of O(n^2), the other solution has a time complexity of O(n). You can achieve a better time complexity using a multi-key dictionary \$\endgroup\$ – Node.JS Jan 30 at 6:06
11
\$\begingroup\$

A couple of small things to add:

  • Maybe not applicable to a timed interview, but inline documentation (///) on public members is always nice, and would help to explain the otherwise vague IsValid method name.

  • I'd want to throw an exception if any other character is encountered, since the behaviour is undefined and undocumented. The spec says to assume only ()[]{} will appear in the string, which means anyone using it incorrectly (by including such characters) should be informed (maybe they assume it handles <> as well?). If a customer were to depend upon this (undocumented) behaviour of just ignoring such characters, you'd have another undocumented 'feature' to maintain in future (or else an unhappy customer).

  • Any reason the method isn't static? Conceptual benefits aside, making it static would make it clear that it's not messing with any state, and makes it easier to use.

  • That's a very limited set of test-cases: you don't test for {} at all.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.