## DEV Community

Posted on • Originally published at alkeshghorpade.me

# LeetCode - Valid Parentheses

### Problem statement

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

Problem statement taken from: https://leetcode.com/problems/valid-parentheses

Example 1:

``````Input: s = "()"
Output: true
``````

Example 2:

``````Input: s = "()[]{}"
Output: true
``````

Example 3:

``````Input: s = "(]"
Output: false
``````

Example 4:

``````Input: s = "([)]"
Output: false
``````

Example 5:

``````Input: s = "{[]}"
Output: true
``````

Constraints:

``````- 1 <= s.length <= 10^4
- s consists of parentheses only '()[]{}'
``````

### Explanation

The problem can be solved by using a stack or by recursion.
For a large string, building up a stack of recursive calls consumes memory temporarily
and may take more space than an iterative solution.

We can use extra storage in the form of a stack and hashmap.
Let's check the algorithm and solution.

#### Stack

``````- initialize stack st and i = 0.

- return true if the string is empty.

- Loop while i < 0
- if s[i] == '(' || s[i] == '[' || s[i] == '{'

// push the char to stack
- st.push(s[i])

- else if s[i] == ')' && !st.empty() && st.top() == '(' ||
s[i] == '}' && !st.empty() && st.top() == '{' ||
s[i] == ']' && !st.empty() && st.top() == '['

// pop the top element if the current char is a closing brace provided
// stack is not empty.
- st.pop()

- else

// the string is not a valid parenthesis
- return false

i++

- return true if st.empty()

- return false.
``````
##### C++ solution
``````class Solution {
public:
bool isValid(string s) {
stack<char> st;

if(s.size() == 0){
return true;
}

int i = 0;
while(i < s.size()){
if( s[i] == '(' || s[i] == '[' || s[i] == '{' ){
st.push(s[i]);
} else if ( (s[i] == ')' && !st.empty() && st.top() == '(') ||
(s[i] == '}' && !st.empty() && st.top() == '{') ||
(s[i] == ']' && !st.empty() && st.top() == '[')
){
st.pop();
} else {
return false;
}
i++;
}

if(st.empty()) {
return true;
}

return false;
}
};
``````
##### Golang solution
``````func isValid(s string) bool {
st := []rune{}
bracketsMap := map[rune]rune{
')': '(',
'}': '{',
']': '[',
}

for _, v := range s {
if len(st) == 0 {
st = append(st, v)
continue
}

if bracketsMap[v] == st[len(st)-1] {
st = st[:len(st)-1]
} else {
st = append(st, v)
}
}

return len(st) == 0
}
``````
##### Javascript solution
``````var isValid = function(s) {
let st = [];
const legend = {
'(': ')',
'{': '}',
'[': ']'
};

for (let i = 0; i < s.length; i++) {
if (s[i] === '(' || s[i] === '{' || s[i] === '[') {
st.push(s[i]);
} else if (legend[st.pop()] !== s[i]) {
return false;
}
}

return st.length ? 0 : 1;
};
``````

Let's dry-run our algorithm to see how the solution works.

``````Input:
s = ()[]{}

Step 1: stack<char> st;

Step 2: s.size() == 0
s.size() = 6
6 == 0
false

Step 3: i = 0

Step 4: loop while i < 6
0 < 6
true

// stack is empty
st = []

if s[i] == '(' || s[i] == '[' || s[i] == '{'
true
st.push(s[i])
st.push( '(' )

top
|
st = [ '(' ]

i++
i = 1

Step 5: loop while i < 6
1 < 6
true

top
|
st = [ '(' ]

if s[i] == '(' || s[i] == '[' || s[i] == '{'
false

else if (s[i] == ')' && !st.empty() && st.top() == '(')
true
st.pop()
st = []

i++
i = 2

Step 6: loop while i < 6
2 < 6
true

// stack is empty
st = []

if s[i] == '(' || s[i] == '[' || s[i] == '{'
true
st.push(s[i])
st.push( '[' )

top
|
st = [ '[' ]

i++
i = 3

Step 7: loop while i < 6
3 < 6
true

top
|
st = [ '[' ]

if s[i] == '(' || s[i] == '[' || s[i] == '{'
false

else if (s[i] == ']' && !st.empty() && st.top() == '[')
true
st.pop()
st = []

i++
i = 4

Step 8: loop while i < 6
4 < 6
true

// stack is empty
st = []

if s[i] == '(' || s[i] == '[' || s[i] == '{'
true
st.push(s[i])
st.push( '{' )

top
|
st = [ '{' ]

i++
i = 5

Step 9: loop while i < 6
5 < 6
true

top
|
st = [ '{' ]

if s[i] == '(' || s[i] == '[' || s[i] == '{'
false

else if (s[i] == '}' && !st.empty() && st.top() == '{')
true
st.pop()
st = []

i++
i = 6

Step 10: loop while i < 6
6 < 6
false

Step 11: if st.empty()
true