Valid Parentheses

In this “Valid Parentheses” problem on LeetCode, you are given a string containing only parentheses, brackets, and curly braces. You need to determine if the string’s parentheses are valid and properly balanced. The valid parentheses should be closed in the correct order.

For example, if the input string is {[()]}, it is considered valid because all the opening parentheses have their corresponding closing parentheses in the correct order. However, if the input string is {[()]} or {[(])}, it is considered invalid because the parentheses are not properly balanced.

To solve this problem, you can use a stack data structure. You iterate over the characters of the string and perform the following steps:

1. If the current character is an opening parentheses (i.e., (, {, or [), push it onto the stack.
2. If the current character is a closing parentheses (i.e., ), }, or ]), check if the stack is empty. If it is empty, or the top of the stack does not match the current character as a valid pair, the parentheses are invalid. Return false.
3. If the top of the stack matches the current character as a valid pair, pop the top element from the stack.
4. After iterating through all the characters, check if the stack is empty. If it is empty, return true; otherwise, return false.

The time complexity of above solution is O(n), where n is the length of the input string, and the space complexity is O(n) as well.

The problem tests your understanding of stack operations and string manipulation to determine the validity of parentheses. It’s a common problem used to assess algorithmic and data structure skills in programming interviews and coding challenges.

Here’s solution in C++:

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

bool isValid(string s) {
  stack<char> parentheses;
  unordered_map<char, char> closingMap = {
    {')', '('}, {']', '['}, {'}', '{'}
  };

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