Valid Parenthesis

Parents : Leetcode

Siblings :

Date and time note was created	$= dv.current().file.ctime
Date and time note was modified	$= dv.current().file.mtime

Question Link : 20. Valid Parentheses

Question Breakdown

• We need to validate if a string of parenthesis given is a valid string or not.
• A string of parenthesis is valid iff
  • Closing and Opening are of same type.
  • The order of closing and opening is correct i.e
    • [ ( ) ] is correct order
    • [ ( ] ) ] is incorrect order as for ] , [ must be before

Approaches

Brute Force/Optimised approach

Algorithm

Intuition: Some type of technique to be used where I can access previous value and check it with current value and remove previous value in correct order.

As previous value is to be accessed and removed we can think of it as some sort of last in first out terms i.e top element gets removed and inserted first.

Such functionality is implemented using a data-structure called Stack

Steps:

• Take a stack
• push if its an open bracket
• return false
  • if stack is empty i.e it contains no elements or only closing brackets.
  • if for closing bracket wrong opening bracket is at top of stack.
• else pop the element
• return stack is empty or not.// as it would only tell us if all the brackets have been resolved.

Code

// #identification : As we can see that we need to traverse the string such that whenever a closing bracket is occured and the the bracket before it matches then we need to remove the opening bracket from the front i.e LIFO (last in first out). so we would use the data structure appropriate for it that is stack data structure. 
    bool isValid(string s) {
          stack<char>stk;
          for(auto&it:s){
              if(it=='('||it=='['||it=='{')
                  stk.push(it);
              else if(stk.empty()||
                       it==')'&&stk.top()!='('||
                       it=='}'&&stk.top()!='{'||
                       it==']'&&stk.top()!='['
                      )
                        return false;        
             else stk.pop(); 
          }
            return stk.empty();  
    } 

Time Complexity

$O(N)$ For traversal

Space Complexity

$O(N)$ For stack used.

References

Foot notes