Problem Statement

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

Valid Parentheses - LeetCode

Approach

  1. Iterate over the characters of the string.
  2. If the character is an opening bracket, append it’s corresponding closing bracket to the stack.
  3. If the character is a closing bracket, pop the last element from the stack and compare it with the character.
  4. If the characters do not match, return false.
  5. If the stack is empty at the end, return true. Otherwise, return false.

Solution in Swift

class Solution {
    func isValid(_ s: String) -> Bool {
        var stack: [Character] = []
        for char in s {
            switch char {
            case "(":
                stack.append(")")
            case "{":
                stack.append("}")
            case "[":
                stack.append("]")
            default:
                if stack.popLast() != char { return false }
            }
        }
        return stack.isEmpty
    }
}

Complexity

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)