Skip to main content

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 from this blog

Globant part 1

 1)call,apply,bind example? Ans: a. call Method: The call method is used to call a function with a given this value and arguments provided individually. Javascript code: function greet(name) {   console.log(`Hello, ${name}! I am ${this.role}.`); } const person = {   role: 'developer' }; greet.call(person, 'Alice'); // Output: Hello, Alice! I am developer. In this example, call invokes the greet function with person as the this value and passes 'Alice' as an argument. b. apply Method: The apply method is similar to call, but it accepts arguments as an array. Javascript code: function introduce(language1, language2) {   console.log(`I can code in ${language1} and ${language2}. I am ${this.name}.`); } const coder = {   name: 'Bob' }; introduce.apply(coder, ['JavaScript', 'Python']); // Output: I can code in JavaScript and Python. I am Bob. Here, apply is used to invoke introduce with coder as this and an array ['JavaScript', 'Pyt...
Post a Comment
Read more

Node.js: Extract text from image using Tesseract.

In this article, we will see how to extract text from images using Tesseract . So let's start with this use-case, Suppose you have 300 screenshot images in your mobile which has an email attribute that you need for some reason like growing your network or for email marketing. To get an email from all these images manually into CSV or excel will take a lot of time. So now we will check how to automate this thing. First, you need to install Tesseract OCR( An optical character recognition engine ) pre-built binary package for a particular OS. I have tested it for Windows 10. For Windows 10, you can install  it from here. For other OS you make check  this link. So once you install Tesseract from windows setup, you also need to set path variable probably, 'C:\Program Files\Tesseract-OCR' to access it from any location. Then you need to install textract library from npm. To read the path of these 300 images we can select all images and can rename it to som...
1 comment
Read more

CSS INTERVIEW QUESTIONS SET 2

  You make also like this CSS interview question set 1. Let's begin with set 2, 5)What is the difference between opacity 0 vs display none vs visibility hidden? Property           | occupies space | consumes clicks | +--------------------+----------------+-----------------+ | opacity: 0         |        yes      |        yes       | +--------------------+----------------+-----------------+ | visibility: hidden |        yes       |        no        | +--------------------+----------------+-----------------+ | display: none      |        no       |        no        | When we say it consumes click, that means it also consumes other pointer-events like onmousedown,onmousemove, etc. In e...
Post a Comment
Read more