Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

Justify if a string consists of valid parentheses

You are given an array of strings. Each of these strings is made up of bracket characters only :
'(', ')', '{',  '}',  '[',  ']'.

Programming languages utilize these brackets in balanced pairs, so the following rules are always followed :

  • Every opening bracket has a corresponding closing bracket : '(' with ')', '{' with '}', and '[' with ']'
  • Two brackets form a pair if they have no open bracket of any type between them.
  • For example: '[}]' is invalid, '[{}]' is valid. 
  • The closing bracket of a pair must be of the same type as the opening bracket, e.g. '( )' is valid, but '[ )' is not valid.

Your task is to determine if of the strings of brackets in the input array are valid or invalid by these criteria.
  

Sample Input / Output:

// Input :
[
  "{}[]()",
  "{[}]"
] 

// Output : 
[ "YES", "NO" ]

// Input :
[
   "{[}]",
   "[{()()}({[]})]({}[({})])((((((()[])){}))[]{{{({({({{{{{{}}}}}})})})}}}))[][][]",
   "{}[]()"
] 

// Output : 
["NO","YES","YES"]

Logic :

  • Declare a character stack S.
  • Traverse the string experssion.
    • If the current character is an opening bracket ( or { or [ then push it to stack.
    • If the current character is a closing bracket ) or } or ] then pop from stack and if the popped character is the matching starting bracket then fine
    • else continue.
  • At the end of the traversal, if there is some opening bracket left in stack then the string is “not balanced”. Hence, return false.

Solution :

Approach 1 :


Approach 2 : Using Map data structure. Map is a new data structure introduce in ES6. There is a subtle difference between these two data structures. More details doing the comparison between these two data structures can be found here.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *