# Valid Parentheses LeetCode Solution

Difficulty Level Easy
BufferedOutputStream StringViews 11479

In Valid Parentheses LeetCode problem we have given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. Here we will provide a Valid Parentheses LeetCode Solution to you.

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.
• ()][ not valid
• (){[]} valid
• [(){}] valid

## Example

Input: str = “[]{()()}”

Output: The given string contains valid parentheses.

## Algorithm for Valid Parentheses

n: length of string

str: input string

1. Declare and initialize a stack S.
2. Run a loop on i from 0 to n.
1. If str[i] is an opening bracket, then push str[i] in the stack.
2. If str[i] is a closing bracket, then there are two possibilities:
• If the top bracket present in the stack is the opening bracket of the same type, then pop top element of the stack.
• Else, return false.
3. Return S.empty().

## Working Process Step By Step

str = [{}()]

n = 6

Step 1: we get opening bracket [, hence push [ in stack.

Step 2: we get opening bracket {,hence push { in stack.

Step 3: we get a closing bracket } and the top of the stack is {, hence do pop operation on the stack.

Step 4: we get opening bracket (, hence push ( in the stack.

Step 5: we get a closing bracket ) and the top of the stack is (, hence do pop operation on the stack.

Step 6: we get a closing bracket ] and the top of the stack is [, hence do pop operation on the stack.

## Implementation for Valid Parentheses LeetCode Solution

### C++ program for Valid Parentheses

```#include<bits/stdc++.h>
using namespace std;
bool isValid(string s) {
stack<char> bracket;
for (char& c : s) {
switch (c) {
case '(': bracket.push(c); break;
case '{': bracket.push(c); break;
case '[': bracket.push(c); break;
case ')': if (bracket.empty() || bracket.top()!='(') return false; else bracket.pop(); break;
case '}': if (bracket.empty() || bracket.top()!='{') return false; else bracket.pop(); break;
case ']': if (bracket.empty() || bracket.top()!='[') return false; else bracket.pop(); break;
default: ;
}
}
return bracket.empty() ;
}
int main(){
string s = "[[]{}]()";
bool check = isValid(s);
if(check){
cout<<"The given string contains valid parentheses.";
}
else{
cout<<"The given string contains invalid parentheses.";
}
}
```
`The given string contains valid parentheses.`

### JAVA program for Valid Parentheses

```import java.util.*;
public class Main
{
public static boolean isValid(String s) {
Stack<Character> bracket = new Stack<>();
for (char c : s.toCharArray()) {
switch (c) {
case '(': bracket.push(c); break;
case '{': bracket.push(c); break;
case '[': bracket.push(c); break;
case ')': if (bracket.empty() || bracket.peek()!='(') return false; else bracket.pop(); break;
case '}': if (bracket.empty() || bracket.peek()!='{') return false; else bracket.pop(); break;
case ']': if (bracket.empty() || bracket.peek()!='[') return false; else bracket.pop(); break;
default: ;
}
}
return bracket.isEmpty();
}
public static void main(String[] args) {
String s = "{}[)(]";
boolean check = isValid(s);
if(check){
System.out.println("The given string contains valid parentheses.");
}
else{
System.out.println("The given string contains invalid parentheses.");
}
}
}
```
`The given string contains invalid parentheses.`

### Complexity

#### Time complexity

O(n)

where n is the length of the given string as we are traversing the given string for once.

The pop(), top() and push() operation in stack takes constant time.

#### Space complexity

O(n)

As we can use an extra space of stack and in the worst case, the size of the stack can be n/2

References

Translate »