Swift Coding Puzzles #2 – Balanced Brackets

This is part of a series of coding puzzles inspired by the #CodingPuzzle tag/puzzles originally curated and shared by Ali Spittel. This is my approach to solving those puzzles in Swift. If you have any comments or answers you want to share, post them below! I’d love to read them.

---

Puzzle #2

Given strings of brackets, determine whether each sequence of brackets is balanced.

When would you come across a situation like this? Well, if you ever write a source editor, you might come across something like this. As most programming languages use brackets to denote context, functions, and other divisions, we’ve probably all come across a situation where we forgot to close something off.

For the sake of this exercise, let’s define what brackets mean. In this case, it’ll be three sets of characters: ( ) , [ ] , and { } . The first character we’ll call the “open bracket” and the latter the “close bracket”.

So, what makes a balanced sequence?

1. A matched pair of brackets.
2. Any nested brackets must also be matched pairs.

An example of some balanced sequences include: () , [(){}] , {([()])}

An example of some imbalanced sequences include: (() , [([)]] , {([)]}

If any of those become unpaired, then the entire sequence is considered imbalanced. If you’ve ever created a class in Swift and forgot to close a brace when defining functions, you’ll know what that is.

By the above definitions, we can thus determine that in a balanced sequence:

1. It has an even number of brackets
2. An open bracket will never meet a close bracket of a different type
3. A closed bracket will never appear before its corresponding open bracket

That said, here’s how I approached the problem.

First, I defined what each of the brackets were.

let brackets: [Character: Character] = [
    "[":"]",
    "(":")",
    "{":"}"
]
var openBrackets: [Character] { return Array(brackets.keys) as! [Character] }
var closeBrackets: [Character] { return Array(brackets.values) as! [Character] }

Using a dictionary, I’ll be able to easily look up the close bracket for a given open bracket.

Next, let’s look at my function to solve this.

func isBalanced(_ string: String) -> Bool {
    if string.count % 2 != 0 { return false }
    var stack: [Character] = []
    for character in string {
        if closeBrackets.contains(character) {
            if stack.isEmpty {
                return false
            } else {
                let indexOfLastCharacter = stack.endIndex - 1
                let lastCharacterOnStack = stack[indexOfLastCharacter]
                if character == brackets[lastCharacterOnStack] {
                    stack.removeLast()
                } else {
                    return false
                }
            }
        }
        if openBrackets.contains(character) {
            stack.append(character)
        }
    }
    
    return stack.isEmpty
}

First, if the string has an odd number of characters, we automatically fail it. This is in line with point number 1 above.

I then declare a variable to temporarily hold brackets. This stack will be used in the following loop.

Next, we go through each character of the string. Our first check is whether the character is a close bracket or not. If it is, and our stack is empty, it means we’re encountering a close bracket before its open bracket counterpart. We thus return false. If the stack isn’t empty, we check if the last character on the stack is an open counterpart of this close bracket. If it is, we remove the open bracket from the stack. Otherwise, we return false.

If it’s not a close bracket, we’re likely looking at an open bracket. Those automatically get added to the stack.

This loop functions for all characters in the string. Afterwards, our return is whether or not the stack is empty. If it’s not empty, it meant we had more open brackets than closed brackets, and while the earlier catches may not have produced a return, it technically is an unbalanced bracket set.

Here are a few sample calls to this function and their outputs.

isBalanced("()") // True
isBalanced("[]") // True
isBalanced("][") // False
isBalanced("[][") // False
isBalanced("()()") // True
isBalanced("[(){}]") // True
isBalanced("{{[()()][]}}") // True
isBalanced("[]()({)}") // False
isBalanced("(((") // False

I had initially hoped to tackle this with recursion, but I found the above solution to be easier to follow and much easier to manage.

Did you have a different solution? Is there something I could improve with my Swift code? I’d love to hear from you!

• Category: Development
• Tag: #CodingPuzzle, Swift