Valid Parenthesis

Instructions

Given a string s containing just 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

Input: s = "()[]{}"
Output: true

Input: s = "(]"
Output: false

Approach

In this problem, we are mainly concerned about the most recent parenthesis we encounter such that if it is a closing parenthesis, we match it to an open parenthesis previously encountered. If there is no open parenthesis occurring before the closing, then the string is not a valid parenthesis.

Since we are interested in the most recent character, we can use the stack data structure, which implements Last In First Out (LIFO) behavior.
Therefore, the last item to go into the stack is the first to be removed.

So we push the open parenthesis, and when we encounter its matching closing parenthesis, we pop it (the opening parenthesis) from the stack.

For a valid parenthesis string s, the end result will be an empty stack; if the stack is not empty, then s is not a valid parenthesis.

Python Implementation

• Breakdown

• Initialize stack to add and pop from

• Initialize a dictionary of the brackets where closing is the key and opening is the value.

• Loop through given string; if element in string is in the dictionary keys, check if the stack is empty
  and if element at stack[-1] ie most recent element is equal to element at dict[i] and remove this bracket from the stack.
  Note: if the stack is empty we return False because a valid string cannot begin with a closing parenthesis.

• if the above conditions are not met we immediately return false
  else we append to the stack because that means the element in the string is an opening parenthesis.

Code

def isValid(self, s):        
    parentheses = {'}': '{', ']': '[', ')': '('}
    stack = []
     for i in s:
         if i in parentheses:
            if stack and stack[-1] == parentheses[i]:
               stack.pop()
             else:
                 return False
         else:
             stack.append(i)
     return not stack

Time Complexity

O(n)
The algorithm scales linearly as the input increases.

Space Complexity

The space complexity is O(n) because, in the worst-case scenario where all elements are opening brackets, we will have to store n elements in the stack.