### Data structure problem 2 (Stack): Valid Parentheses problem.

This is one of the interview questions asked in the technical or data structure round which can be solved using stack.

As we know **stack is first in last out**.

You may also like this: Data structure problem 1.

So let's begin with the problem statement,

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

**Examples :**

a)Input: s = "()"

Output: true

Example 2:

b)Input: s = "()[]{}"

Output: true

Example 3:

c)Input: s = "(]"

Output: false

**Solution:**

var isValid = function (s) { const obj = { "}": "{", "]": "[", ")": "(", }, var stack = []; //As javascript array behaves like stack for (let i = 0; i < s.length; i++) { if (s[i] in obj) {//check 1 if (!stack.length || stack[stack.length - 1] !== obj[s[i]]) {//check 3 return false; } else stack.pop();//check 4 } else{ stack.push(s[i]);//check 2 } } return !stack.length;//check 5 };

Logic:

**We know in the javascript string can be accessed like an array.**

Suppose

s = "(]"

We have used a loop to iterate a string,

We have maintained a map object which has closing brackets as keys.

const obj={

"}":"{",

"]":"[",

")":"(",

}

**1st iteration:**

In check 1 we have a check for '(' present in obj.

It is not present so we have pushed '(' in the stack (**check 2** executed).

**2nd iteration:**

In check 1 we have a check for ']' present in obj.

It is present. So moving towards **check 3** we have used **2 OR conditions.**

**Why these 2 OR conditions?**

**1st is** if the stack is empty then return false. (That means there was nothing in the stack. There might be a case where s='}{}'. So here the first bracket is the closing bracket so no need to check further as we can conclude that it is not a valid string so return false)

**2nd** is if stack not empty but if the last element in the stack is not equal to obj[s[i]] then return false(Not valid . Mismatch in order of opening and closing).

That means if s='{}'

then the stack will contain { in 1st iteration. So in the second iteration stack length will not be empty but obj[s[i]]==stack[stack.length-1]. So we will execute **check 4 (pop the stack). So in this case where s='{}' stack will be empty after all iterations i.e 2. **We will **execute check 5** and will return true as !stack. length(0) will be true.

**Let's come back to our example where s='(]' 2nd interaction:**

**Here the 2nd OR condition will satisfy which means it is not a valid string(mismatch in order so return false).**

I hope you like this article. Please stay connected for more such articles.

If any doubts please let me know in the comment section.

You can also follow me on **Twitter** or **Linkedin **for** **the** **latest updates.

**Saurabh Joshi**

## Comments

## Post a Comment