LESSON 322 OF 415 · STACK

Valid Parentheses in Swift: O(n) with a Stack

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Example 1:

Input: input = "()"
Output: true

Example 2:

Input: input = "()[]{}"
Output: true

Example 3:

Input: input = "(]"
Output: false

Example 4:

Input: input = "([)]"
Output: false

Example 5:

Input: input = "{[]}"
Output: true

Constraints:

The length of input is between 1 and 10⁴.
input consists of parentheses only '()[]{}'.

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 11

Guided

Ctrl + Enter to check

SWIFT · STACK

Valid Parentheses in Swift, explained

Problem overview

The method isValid receives a string, input, made only of the characters (, ), {, }, [ and ]. It returns true when the brackets are balanced, which takes two conditions: every opening bracket is closed by a bracket of the same type, and brackets are closed in the right order.

The strings "()", "()[]{}" and "{[]}" are valid. The string "(]" is not, because the types differ. The string "([)]" is not either: each opening bracket has a partner of the right type, but the ) arrives while the [ is still open, so the order is wrong.

The lesson asks for O(n) time and O(n) extra space.

Approach: match each closer with the latest opener

Look at "{[]}". The first closing bracket, ], must close the most recent opening bracket, the [. After that, the } must close the {, which is now the most recent one still open. Whenever a closing bracket appears, the bracket it has to match is always the latest unmatched opener. That is exactly what a stack provides.

The algorithm reads the string from left to right:

An opening bracket goes on the stack, where it waits.
A closing bracket takes the top of the stack, and the two must be a matching pair. If the stack is empty, or the top is a different type, the string is invalid.
When the string ends, the stack must be empty. Any bracket left on it was never closed.

A dictionary that maps each opening bracket to its closing one keeps the matching rules in one place, so the code needs no chain of comparisons.

Step by step

Write the pairs. A constant closingBrackets of type [Character: Character] maps "(" to ")", "{" to "}" and "[" to "]", one pair per line. The type annotation makes the literals Character values rather than String values.
Create the stack. var stack: [Character] = []. The last element is the top: append and removeLast work at that end.
Loop over the characters. for bracket in input gives one Character at a time.
Recognise an opener. A character is an opening bracket when it is a key of the dictionary: closingBrackets[bracket] != nil. A missing key gives nil.
Push it. stack.append(bracket).
Handle everything else in the else branch. Write } else { on one line. Here bracket is a closing bracket.
Reject an unmatched closer. If stack.isEmpty, return false: nothing is open for it to close.
Pop the latest opener. let openBracket = stack.removeLast(). The emptiness check above is what makes this safe.
Compare. If bracket != closingBrackets[openBracket], return false. The types don't match.
Check for leftovers. After the loop, return stack.isEmpty.

The solution in Swift

class Solution {
    func isValid(_ input: String) -> Bool {
        let closingBrackets: [Character: Character] = [
            "(": ")",
            "{": "}",
            "[": "]"
        ]
        var stack: [Character] = []

        for bracket in input {
            if closingBrackets[bracket] != nil {
                stack.append(bracket)
            } else {
                if stack.isEmpty {
                    return false
                }
                let openBracket = stack.removeLast()
                if bracket != closingBrackets[openBracket] {
                    return false
                }
            }
        }

        return stack.isEmpty
    }
}

The Swift details worth a closer look:

Character versus String. Iterating over a String yields Character values, so the dictionary is keyed by Character. Without the annotation, Swift would read "(" as a String literal and the lookup closingBrackets[bracket] would not compile.
Dictionary lookups are optional. closingBrackets[bracket] is a Character?, which is nil for a key that isn't there. The comparison != nil turns that into a yes or no.
Comparing an optional with a value. bracket != closingBrackets[openBracket] compares a Character with a Character?. Swift lets you do this without unwrapping: the comparison is true when the optional is nil or holds a different character.
Constants and variables. The dictionary never changes, so it is a let. The stack changes, so it is a var.
removeLast() on an empty array crashes. The isEmpty check right before it prevents that. Swift also offers popLast(), which returns nil instead of crashing.
No indexing a string by number. The solution never writes input[i], which Swift doesn't allow with an Int. The for-in loop is the idiomatic way to visit each character.

Complexity

Time: O(n). Each character is visited once, and a push, a pop and a dictionary lookup each take constant time on average.

Space: O(n). In the worst case, such as a string made only of opening brackets, the stack holds every character.

Edge cases and common mistakes

A closer first. ")" returns false: the stack is empty when the closer arrives.
Unclosed openers. "((" and "(" return false because the stack is not empty at the end. Returning true right after the loop would be a bug.
Closing in the wrong order. "][" fails at the first character, and "([)]" fails when ) meets [ on top of the stack.
Counting instead of stacking. Counting each bracket type separately accepts "([)]", which is invalid. The order matters, so a plain counter isn't enough.
The empty string. It has no brackets to mismatch, so the method returns true. The lesson's constraints promise at least one character, so this is not tested there.
Popping without checking. Calling removeLast() on an empty stack crashes the program instead of returning false.

Testing

"()" gives true.
"()[]{}" gives true.
"{[]}" gives true.
"(]" gives false.
"([)]" gives false.
"((" gives false.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free