### 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**

Excellent data with lots of information. I have bookmarked this page for my future reference. Do share more updates.

ReplyDeleteFull Stack Developer Course in Chennai

Full Stack Developer Online Course

Full Stack Online Course

Full Stack Development Online Course