DSA in Swift: Braces in given array are balanced or not

Swift: Solving the "Valid Parentheses" Problem

Problem: Valid Parentheses

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

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Examples:

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

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

Swift Solution

class Solution {
    func isValid(_ s: String) -> Bool {
        // Stack to keep track of opening brackets
        var stack: [Character] = []
        
        // Dictionary to map closing brackets to opening brackets
        let bracketPairs: [Character: Character] = [
            ")": "(",
            "}": "{",
            "]": "["
        ]
        
        // Iterate through each character in the string
        for char in s {
            // If it's a closing bracket
            if let openingBracket = bracketPairs[char] {
                // Check if stack is empty or top doesn't match
                if stack.isEmpty || stack.removeLast() != openingBracket {
                    return false
                }
            } else {
                // If it's an opening bracket, push to stack
                stack.append(char)
            }
        }
        
        // String is only valid if stack is empty
        return stack.isEmpty
    }
}

// Example usage
let solution = Solution()
print(solution.isValid("()"))        // true
print(solution.isValid("()[]{}"))    // true
print(solution.isValid("(]"))        // false
print(solution.isValid("([)]"))      // false
print(solution.isValid("{[]}"))      // true

Explanation

This solution uses a stack data structure to solve the problem efficiently. Here's how it works:

1. We create a stack to store opening brackets as we encounter them.

2. We use a dictionary to map closing brackets to their corresponding opening brackets.

3. For each character in the string:

- If it's a closing bracket:

* Check if the stack is empty (if so, return false)

* Check if the last opening bracket matches (if not, return false)

- If it's an opening bracket:

* Push it onto the stack

4. Finally, check if the stack is empty (all brackets were properly closed)

Time Complexity: O(n) where n is the length of the string

Space Complexity: O(n) to store the stack in worst case

• Whatsapp
• Tweet
• Share
• Share
• Share
• Share

Sign up here with your email