Validating Balanced Brackets: Two Approaches in Python

In this post, we’ll explore two distinct methods to validate if a given string contains balanced brackets.

First Solution: Using String Replacement The first solution involves repeatedly replacing matched bracket pairs in the string until no more pairs can be found.

class Solution:
    def isValid(self, s: str) -> bool:
        size = len(s)
        
        # If the string length is odd, it's impossible for the brackets to be balanced
        if size % 2 == 1:
            return False
        
        # Continuously replace balanced bracket pairs
        while s.__contains__("{}") or s.__contains__("[]") or s.__contains__("()"):
            s = s.replace("()", "")
            s = s.replace("{}", "")
            s = s.replace("[]", "")

        # If all bracket pairs are removed, the string should be empty
        return len(s) == 0

# ⏰48 ms / 🖥️16.2 MB

This solution works by taking advantage of Python’s string replacement. If at the end of all replacements the string is empty, it means all brackets were balanced.

Second Solution: Using a Stack The second solution involves using a stack data structure to keep track of opening brackets and ensure they match with the correct closing brackets.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        # Mapping of closing brackets to their corresponding opening brackets
        bracket_map = {")": "(", "]": "[", "}": "{"}

        for char in s:
            # If the current character is a closing bracket
            if char in bracket_map:
                # Pop the top element from stack if it's not empty; otherwise, assign a dummy value
                top_element = stack.pop() if stack else "#"
                
                # Check if the popped element matches the current bracket's counterpart
                if bracket_map[char] != top_element:
                    return False
            else:
                # Push the opening bracket onto the stack
                stack.append(char)

        # The stack should be empty at the end for the brackets to be balanced
        return not stack

# ⏰38 ms / 🖥️16.3 MB

The stack-based approach is often considered more efficient for this problem since it can determine if the string is unbalanced more quickly in many cases, without needing to traverse the entire string.

Conclusion

Both methods offer valid ways to solve the problem, with the stack-based approach being more common in algorithm and data structure discussions. Choose the one that you find more intuitive or the one that best fits the specific requirements of your application.