# Leetcode: Valid parentheses

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.

• Should IsValidReview(")(")); be true? Jan 29 '19 at 12:58

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.

• Cool thanks I was wondering if switch case is the way to go or not Jan 29 '19 at 10:52
• @Gilad I think a Dictionary would suit well. Check my answer too. Jan 29 '19 at 12:59
• @Henrik Hansen code review just twitted your answer to my question this is why we are getting so many +1s good job! Jan 29 '19 at 20:54
• @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. Jan 29 '19 at 23:27
• @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. Jan 30 '19 at 5:19

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!

• 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. Jan 29 '19 at 22:25
• 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. Jan 29 '19 at 23:31
• Sure, the switch solution has magic strings, but it's 1. faster/more performant (1 less object) and 2. more readable Jan 30 '19 at 5:35
• 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 Jan 30 '19 at 5:35
• @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 Jan 30 '19 at 6:06

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.