# Solution For Valid Parentheses

Problem Description:

Given a string 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.

Note that an empty string is also considered valid.

Example:
Input: “()[]{}”
Output: true

Solution Approach:

This problem can be solved using a stack data structure. We can process the string character by character and push every opening bracket onto the stack. Whenever we encounter a closing bracket, we can check if the top of the stack matches the corresponding opening bracket. If it does, we can pop the opening bracket from the stack. If it doesn’t match, we return false since the string is not valid.

At the end, if the stack is empty, it means all brackets are properly terminated, thus our string is valid, otherwise, the string is invalid.

Here is the solution in Python:

“`python
class Solution:
def isValid(self, s: str) -> bool:
stack = [] # initializing our stack
brackets = {‘(‘: ‘)’, ‘{‘: ‘}’, ‘[‘: ‘]’} # a hash-map to quickly compare opening and closing brackets

``````    for char in s:
if char in brackets: # if we have a opening bracket, append it to our stack
stack.append(char)
elif stack and brackets[stack[-1]] == char: # if we have a closing bracket, check if the top of the stack has a matching opening bracket
stack.pop()
else: # if we have a unexpected character
return False

return not stack # returns true only if the stack is empty
``````

“`

Time and Space complexity:

The time complexity of this algorithm is O(n) since we process each character in the input string once. The space complexity is also O(n) since in a worst-case scenario, we might need to store all the opening brackets in the stack.

## Step by Step Implementation For Valid Parentheses

```class Solution {
public boolean isValid(String s) {
// create a stack to store opening parentheses
Stack stack = new Stack<>();

// loop through the string
for (int i = 0; i < s.length(); i++) {
// get the current character
char c = s.charAt(i);

// if the current character is an opening parentheses
if (c == '(' || c == '{' || c == '[') {
// push it onto the stack
stack.push(c);
}
// if the current character is a closing parentheses
else if (c == ')' || c == '}' || c == ']') {
// if the stack is empty, return false
if (stack.isEmpty()) {
return false;
}
// pop the top element from the stack
char top = stack.pop();
// if the current character and the top element from the stack don't match, return false
if (c == ')' && top != '(' || c == '}' && top != '{' || c == ']' && top != '[') {
return false;
}
}
}
// if the stack is not empty at the end, return false
if (!stack.isEmpty()) {
return false;
}
// return true
return true;
}
}```
```def isValid(s):
# Initialize a stack to be used in the algorithm.
stack = []

# Hash map for keeping track of mappings. This keeps the code very clean.
# Also makes adding more types of parenthesis easier
mapping = {")": "(", "}": "{", "]": "["}

# For every character in the input string
for char in s:

# If the character is an closing bracket
if char in mapping:

# Pop the topmost element from the stack, if it is non empty
# Otherwise assign a dummy value of '#' to the top_element variable
top_element = stack.pop() if stack else '#'

# The mapping for the opening bracket in our hash and the top
# element of the stack don't match, return False
if mapping[char] != top_element:
return False
else:
# We have an opening bracket, simply push it onto the stack.
stack.append(char)

# In the end, if the stack is empty, then we have a valid expression.
# The stack won't be empty for cases like ((()
return not stack```
```Given a string 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.
Note that an empty string is also considered valid.

function isValid(s) {
// create a stack to store opening parentheses
let stack = [];

// create a map to store mappings of parentheses
let map = {
'(': ')',
'[': ']',
'{': '}'
};

// loop through string
for (let i = 0; i < s.length; i++) {
// if character is an opening parenthesis, push it to the stack
if (s[i] === '(' || s[i] === '[' || s[i] === '{') {
stack.push(s[i]);
}
// if character is a closing parenthesis
else {
// if stack is empty or character doesn't match the top of the stack, return false
if (stack.length === 0 || map[stack.pop()] !== s[i]) {
return false;
}
}
}
// return true if stack is empty
return stack.length === 0;
}```
```class Solution {
public:
bool isValid(string s) {
// create a stack to store the opening parentheses
stack stk;

// iterate through the string
for (char c : s) {
// if we encounter an opening parenthesis, push it onto the stack
if (c == '(' || c == '[' || c == '{') {
stk.push(c);
}
// if we encounter a closing parenthesis...
else {
// if the stack is empty, then this is an invalid parenthesis
if (stk.empty()) {
return false;
}
// pop the top element off the stack
char top = stk.top();
stk.pop();

// if the top element doesn't match the closing parenthesis, then this is an invalid parenthesis
if (c == ')' && top != '(') {
return false;
}
if (c == ']' && top != '[') {
return false;
}
if (c == '}' && top != '{') {
return false;
}
}
}
// if the stack is not empty at the end, then this is an invalid parenthesis
return stk.empty();
}
};```
`using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace valid_parentheses { class Program { static void Main(string[] args) { Console.WriteLine(IsValid("()[]{}")); Console.WriteLine(IsValid("(]")); Console.WriteLine(IsValid("([)]")); Console.ReadKey(); } public static bool IsValid(string s) { //Create a stack to store opening parentheses Stack stack = new Stack(); //Loop through each character in the string for (int i = 0; i < s.Length; i++) { //If the character is an opening parenthesis, push it onto the stack if (s[i] == '(' || s[i] == '[' || s[i] == '{') { stack.Push(s[i]); } //If the character is a closing parenthesis else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { //If the stack is empty, that means there were more closing parentheses than opening, so the string is invalid if (stack.Count == 0) { return false; } //If the character is a closing parenthesis that doesn't match the top of the stack, the string is invalid else if (stack.Peek() == '(' && s[i] != ')' || stack.Peek() == '[' && s[i] != ']' || stack.Peek() == '{' && s[i] != '}') { return false; } //Otherwise, pop the top of the stack (since it's a match) and continue checking else { stack.Pop(); } } //If we've made it through the entire string and the stack is empty, the string is valid return stack.Count == 0; } } }`
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]