Imagine you are building a compiler. Before running any code, the compiler must check that the parentheses in the program are balanced. Every opening bracket must have a corresponding closing bracket. We can approximate this using strings.

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

  • Open brackets are closed by the same type of brackets.
  • Open brackets are closed in the correct order.
  • Note that an empty string is also considered valid.

Example:

Input: "((()))"
Output: True

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

Input: "({[)]"
Output: False
class Solution:
    def isValid(self, s):
        #Fill this in.

Idea behind the solution

The solution was inspired by the Shunting yard algorithm from Edsger Dijkstra.

We basically push to the stack any opening bracket and for each closing bracket we verify if the closing bracket matches what is on the top of the stack. If does not match, then return false.

At the end the stack must be empty, so the number of closing bracket matches the number of opening brackets.

This algorithms runs in O(n) where n is the length of the string, and needs O(n) space for the stack.

Please check the Solution.java snippet for the solution.

This solution originally posted at: Github by @Murillo2380