Leetcode - Valid Parentheses

Question

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

An input string is valid if

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

This is astack question.

Idea

• Keep a parentheses map to map closed brackets to their open brackets
• Use a stack to keep track of what parens have been closed off
• Iterate through the string
• If the current char is a closed paren:
  • Check if the stack is empty, if so the closed paren is not valid
  • Check if the last item in the stack is the open paren for the current paren, if so, pop the open paren off the stack
  • Else, add the closed paren to the stack
• Otherwise, for an open paren, add it to the stack
• We only take action on a closed paren
• After the loop, check if there are contents in the stack, if no, not all parens have been closed, return false, else true.

O(n) time and O(n) space since we need a stack that can be at maximum the size of the input string

Solution