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.


Written By:

Saurabh Joshi






Comments

Post a Comment

Popular Posts