You are given a string consisting of characters: '(', ')', '[', ']', '{' and '}'. Write a program to check whether the string is valid or not.

Problem Note:

  • A string if said to be valid if an open parenthesis is closed by the same type of parenthesis.
  • Also, the open parenthesis must be closed in the correct order.
  • Return True if the string is valid, else return False

Example 1

Input: "(([](){}))"
Output: True

Example 2

Input: "([)]"
Output: False
Explanation: The brackets are closed but not in the correct order

Example 3

Input: "()[]({})"
Output: True