This post is completed by 4 users

  • 1
 Add to List
Medium

354. Valid Multiple Parentheses

Objective: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Example:

()()([]({}))[] valid: true
()({]) valid: false
[]{}() valid: true
[(}{)] valid: false

Earlier we had seen problem Valid Parentheses, where only one type of parentheses was present in the input string, in this problem we can have multiple types of parentheses present in the input String. This problem can be considered as extension of Valid Parentheses problem.

Approach:

Using Stack:

  1. Initialize a Stack.
  2. Iterate the input string, one character at a time.
  3. Check if character is open bracket
    1. ‘(‘, if yes then push closed bracket ‘)’ to stack.
    2. ‘[‘, if yes then push closed bracket ‘]’ to stack.
    3. ‘{‘, if yes then push closed bracket ‘}’ to stack
  4. Else check if character is close bracket, either ‘)‘ or ‘]’ or ‘}’  if yes then
    1. Check if stack is empty, if yes return false.
    2. Else if stack is not empty, pop from stack and popped bracket should be same as current bracket else return false.
  5. If at the end stack is empty, return true else return false.
  6. See the image below for more understanding.
Valid Multiple Parentheses

Output:

is input ()()([]({}))[] valid: true
is input ()({]) valid: false
is input []{}() valid: true
is input [(}{)] valid: false

Related Problems: