Table of Contents

## Problem Valid Parentheses

Given a string `s`

containing just the characters `'('`

, `')'`

, `'{'`

, `'}'`

, `'['`

and `']'`

, determine if the input string is valid.

An input string is valid if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.

**Example 1:****Input:** s = “()” **Output:** true

**Example 2:****Input:** s = “()[]{}” **Output:** true

**Example 3:****Input:** s = “(]” **Output:** false

**Constraints:**

`1 <= s.length <= 10`

^{4}`s`

consists of parentheses only`'()[]{}'`

.

## Before solving this problem

Valid parentheses are problem-related to the stack. So before solving that problem, you must be familiar with the concept of stack. I will try to explain them in simple terms. Imagine you have a table and you want to store books in it. In the image below imagine 1, 2, and 3 are books. When you put your first book on the table, You can access it right away.

When you have your second book. You can’t acces book number one without removing book number three here.

Likewise, If you store one more book book number three, book number three will go right after book number two.

And to access all these books, we have to take one book at a time from the table. Book number three will be the first book we can access, book number two after that, and book number one at last. This concept is also known as FILO (First In Last Out)

## Process to solve Valid Parentheses problem

- Valid parentheses are one of the most asked questions from the stack category in an interview. To solve this problem first create a variable which will be our stack. (If your language doesn’t have stack datatype don’t sweat it. They are basically arrays.
- Create a Dictionary to store our Opening and Ending brackets pair. Our ending bracket will be key and our opening bracket will be value here.
- Go through each character in the given string. And if the given character is a value in our dictionary (opening bracket) we will push it to our stack.
- If the given character has a key (Closing bracket) in our dictionary, we will check for our stack Count, or if the current closing parenthesis matches the corresponding opening parenthesis at the top of the stack.
`if (stack.Count == 0 || stack.Pop() != parenthesesMap[c])`

If any of these condition matches we know that this is not a valid string so we will return`false`

. - After our loop completes, we will check if there are any characters left in our
`stack`

. Remember our stack must be empty to be valid. Therefore we will return`true`

if our`stack`

is empty we will return`false`

.

## Solution For Valid Parentheses

```
public class Solution {
public bool IsValid(string s) {
Stack<char> stack = new Stack<char>();
Dictionary<char, char> parenthesesMap = new Dictionary<char, char>
{
{ ')', '(' },
{ ']', '[' },
{ '}', '{' }
};
foreach (char c in s) {
if (parenthesesMap.ContainsValue(c)) {
stack.Push(c);
}
else if (parenthesesMap.ContainsKey(c)) {
if (stack.Count == 0 || stack.Pop() != parenthesesMap[c]) {
return false;
}
}
}
return stack.Count == 0;
}
}
```

## Conclusion

In conclusion, solving the Valid Parentheses problem requires a good understanding of the stack. Make sure to draw the solution on your paper, you can use pictures to relate to this problem. I have used c# in this tutorial to make this problem simple to read and understand. Feel free to use the language of your choice. One of the examples where Valid Parentheses problem is used is a code editor. They might use a more advanced form of this problem. But it is somewhat similar.

We will solve more stack questions in the future so make sure to check our leetcode solution category. Thank you for reading this article. If you find this useful make sure to share it on your social media and don’t forget to check my other articles too.