Balanced brackets | Uber Interview Question & Solution
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
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.