20. Valid Parentheses · LeetCode Solutions solve Now

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:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. 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 <= 104
  • 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.

Valid Parentheses
Stack Example 1

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

Valid Parentheses solution
Stack Example 2

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

Valid Parentheses solution
Stack Example 3

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)

Valid Parentheses solution
Stack Example 4

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.

Leave a Reply

Your email address will not be published. Required fields are marked *