Skip to main content

Daily Coding Problem: Validate a Bracket String

Problem

A string contains only (), [] and {}. Return whether every opening bracket closes in reverse order.

Worked example

{[()]} is valid. ([)] fails when ) meets [.

Read {, [, and ( in that order. The most recent opener must close first, so ) removes (, ] removes [, and } removes {. For ([)], the first closer is ) while [ is still on top. Stop immediately.

How the solution works

The stack holds unmatched openers, with the most recent one on top. An empty stack at the end means no opening bracket remains.

Python stores opening brackets. Java stores the closing bracket it expects, so the two versions enforce the same order. Counting opening and closing brackets alone misses crossed pairs like ([)].

Python solution

def valid_brackets(text):
    closing = {')': '(', ']': '[', '}': '{'}
    stack = []
    for char in text:
        if char not in closing:
            stack.append(char)
        elif not stack or stack.pop() != closing[char]:
            return False
    return not stack

Java solution

import java.util.ArrayDeque;
class Solution {
    static boolean validBrackets(String text) {
        var stack = new ArrayDeque<Character>();
        for (char ch : text.toCharArray()) {
            switch (ch) {
                case '(': stack.push(')'); break;
                case '[': stack.push(']'); break;
                case '{': stack.push('}'); break;
                default: if (stack.isEmpty() || stack.pop() != ch) return false;
            }
        }
        return stack.isEmpty();
    }
}

Complexity and edge cases

O(n) time and O(n) space. Test the empty string, a leading closer, and unmatched opens.

Related exercise: Find the First Unique Character.

Comments

Popular posts from this blog

Minimum Window Substring: Efficient Algorithm for Finding the Shortest Substring

The Minimum Window Substring problem is a classic string manipulation challenge that tests our algorithmic skills. In this blog, we will explore an efficient solution to find the minimum window substring in a given string. We will provide implementation examples in both Java and Python, enabling you to grasp the concepts and apply them to your own coding projects.   Understanding the Problem: Given a string and a target pattern, our objective is to find the minimum window substring in the given string that contains all the characters of the target pattern. The minimum window substring refers to the shortest possible substring that satisfies this condition.   Approach: To solve the Minimum Window Substring problem, we can use the sliding window technique. This approach involves maintaining a window of characters in the string and adjusting its size based on certain conditions. The key steps of the algorithm are as follows: Create two pointers, left and right, to define the windo...