• 0

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:

"([)]" // false
"()" // true

Logic :

  • Declare a character stack S.
  • Traverse the string expression.
  • 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
  • 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.