# Solving the "Valid Parentheses" Problem

Updated May 24, 2023#dsa#leetcode

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.

## C++ Solution

#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();
}

## Swift Solution

func isValid(_ s: String) -> Bool {
var stack = [Character]()
let closingMap: [Character: Character] = [
")": "(", "]": "[", "}": "{"
]

for char in s {
if char == "(" || char == "[" || char == "{" {
stack.append(char)
} else {
if stack.isEmpty || stack.last != closingMap[char] {
return false
}
stack.removeLast()
}
}

return stack.isEmpty
}

## JavaScript Solution

function isValid(s) {
const stack = [];
const closingMap = {
'(': ')',
'[': ']',
'{': '}',
};

for (let i = 0; i < s.length; i++) {
const char = s[i];

if (char === '(' || char === '[' || char === '{') {
stack.push(char);
} else {
if (stack.length === 0 || closingMap[stack.pop()] !== char) {
return false;
}
}
}

return stack.length === 0;
}