Swift Challenge: Check for balanced parenthesis in an expression [Amazon, Microsoft, Visa]

How to code the famous interview question in Swift

Photo by Markus Spiske on Unsplash

You can also read the full story on The Swift Nerd blog using the link below

Interview Question: Check for balanced parentheses in an expression -

Problem Statement

We have to check if a string containing opening and the closing brackets is balanced or not. The string can contain ’(’, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’

A string is said to be balanced if it has as many opening brackets of a certain type as it has closing brackets of that type and if no bracket is unmatched.

Write a function that will take a string as a parameter and return boolean if string is balanced. We will implement this using Swift 5.0

Example

Solution

The problem points to a very interesting data structure called Stack. Since after encountering a closing bracket, we are checked the last processed value if the pair matches, then we are removing it. This problem can be solved very easily using stack. The Stack is LIFO (last in first out) data structure with only one entry and exit point.

Bonus tip: Swift arrays have build-in stack functions like popLast() and last which will be handy

Approach

1. We will iterate the input string and push in the stack if opening brackets are found.
2. On encountering a closing bracket we will check:-
3. If the stack is empty, return false. Since there are no opening brackets to match. (Example, input = “}]]”).
4. We will compare the last stack element with the current character, if it is matching bracket case then we will pop the last element using popLast().
5. Otherwise, we will return false.
6. After exhausting the string ideally, our stack should be empty. If this is non-empty then return false.
7. We will maintain a dictionary to create a mapping for possible matching brackets. Since matching cases are only three, this will help to write clean code and avoid multiple conditions joined using OR.

Steps

1. Initialize the stack and dictionary mapping. I have also created a string containing opening brackets which i will use to identify opening bracket case using contains().

2. Iterating over string and check case for opening brackets.

3. Check the closing brackets case using the last variable on Array and find a suitable match using the dictionary. Pop() the stack if they match.

Code </>

Complexity Analysis

Time: O(n)

For iterating over the string.

Space: O(n)

For stack space.

You can check out the full code with test suites on Github.

Hope you liked this post, please share it with your peers preparing for interviews. Happy Coding!!