Leetcode: 20. Valid Parentheses

Valid Parentheses - LeetCode Solution in C++

In this blog post, we will discuss the problem of checking whether a given string containing parentheses is valid or not. We will provide a solution in C++ for the problem, along with a detailed explanation of the code.

Problem Description

The problem states that we are given a string s that can contain the characters '(', ')', '{', '}', '[', and ']'. We need to determine if the input string is valid, according to the following rules:

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

Approach and Solution

To solve this problem, we can use a stack data structure to keep track of the opening brackets encountered so far. We will iterate through each character in the string and perform the following steps:

• If the character is an opening bracket ('(', '{', or '['), we push it onto the stack.
• If the character is a closing bracket (')', '}', or ']'), we check if the stack is empty or if the top of the stack does not match the corresponding opening bracket. If either condition is true, the string is not valid, and we return false.
• If the character is a closing bracket and the top of the stack matches the corresponding opening bracket, we pop the top element from the stack.

After processing all characters in the string, we check if the stack is empty. If it is, all opening brackets have been closed in the correct order, and the string is considered valid. Otherwise, there are unmatched opening brackets, and the string is not valid.

Here is the C++ code that implements the above approach:

    
      class Solution {
      public:
          bool isValid(string s) {
              stack<char> stk; 
              unordered_map<char, char> mappings = {
                  {')','('},
                  {'}','{'},
                  {']','['}
              };

              for (char c:s)
              {
                  if (c=='(' || c == '{' || c == '[')
                  {
                      stk.push(c);
                  }
                  else 
                  {
                      if (stk.empty() || stk.top() != mappings[c])
                      {
                          return false;
                      }
                      stk.pop();
                  }
              }
              return stk.empty();
          }
      };
    
  

Complexity Analysis

The time complexity of this solution is O(n), where n is the length of the input string. We iterate through each character in the string once.

The space complexity is O(n) as well, as the maximum number of elements that can be stored in the stack is n/2 (in the case of all opening brackets). Additionally, we use an unordered map to store the mappings of opening and closing