Leetcode: Valid parentheses

Question

Leetcode: 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.

Answer 1

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.

Answer 2

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!

Answer 3

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.