Master this coding interview question with a step-by-step solution in multiple languages.
Table of Contents
In programming, checking whether a string contains properly closed brackets (or balanced parentheses) is a common problem. Balanced parentheses mean that each opening bracket (like {, [, or () must have a corresponding closing bracket (}, ], or )) in the correct order. This problem is often referred to as the “balanced parentheses problem,” and it is useful in many scenarios, such as validating mathematical expressions or checking code structure.
In this article, we’ll look at how to solve this problem in multiple programming languages. We’ll be using two test strings:
{{[{]}}– Incorrect (imbalanced brackets){[{()}]}– Correct (balanced brackets)
Understanding the Problem
To ensure a string has properly closed brackets, every opening bracket must have a corresponding closing bracket in the correct order.
Example
Valid Strings:"{[()]}", "[]", "({[{}]})"
Invalid Strings:"{[}", "{{[[(())]]}", "{{[{]}}"
Common Brackets to Check:
- Parentheses:
() - Curly Braces:
{} - Square Brackets:
[]
Approach to Solve the Problem
The most efficient approach uses a stack, a data structure that operates on the Last In, First Out (LIFO) principle.
Algorithm:
- Traverse the string character by character.
- Push opening brackets onto the stack.
- When encountering a closing bracket, check:
- Is the stack empty? If yes, return false (unmatched closing bracket).
- Does the top of the stack match the closing bracket? If no, return false.
- If yes, pop the stack.
- At the end, the stack should be empty.
Time and Space Complexity
- Time Complexity: O(n), where n is the length of the string. Each character is processed once.
- Space Complexity: O(n) in the worst case (all opening brackets are stored in the stack).
Implementation in Multiple Programming Languages
Python
def is_valid_brackets(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping.values():
stack.append(char)
elif char in mapping.keys():
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
return not stack
# Test cases
print(is_valid_brackets("{[()]}")) # Output: True
print(is_valid_brackets("{[}]")) # Output: False
Java
import java.util.Stack;
public class BracketValidator {
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("{[()]}")); // Output: true
System.out.println(isValid("{[}]")); // Output: false
}
}
JavaScript
function isValidBrackets(s) {
const stack = [];
const mapping = { ')': '(', '}': '{', ']': '[' };
for (let char of s) {
if (Object.values(mapping).includes(char)) {
stack.push(char);
} else if (Object.keys(mapping).includes(char)) {
if (!stack.length || stack.pop() !== mapping[char]) {
return false;
}
}
}
return stack.length === 0;
}
// Test cases
console.log(isValidBrackets("{[()]}")); // Output: true
console.log(isValidBrackets("{[}]")); // Output: false
C++
#include <iostream>
#include <stack>
#include <unordered_map>
bool isValidBrackets(const std::string& s) {
std::stack<char> stack;
std::unordered_map<char, char> mapping = {{')', '('}, {'}', '{'}, {']', '['}};
for (char c : s) {
if (mapping.count(c)) {
if (stack.empty() || stack.top() != mapping[c]) {
return false;
}
stack.pop();
} else {
stack.push(c);
}
}
return stack.empty();
}
int main() {
std::cout << isValidBrackets("{[()]}") << std::endl; // Output: 1 (true)
std::cout << isValidBrackets("{[}]") << std::endl; // Output: 0 (false)
}
C#
using System;
using System.Collections.Generic;
class Program {
static bool IsValidBrackets(string s) {
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (c == '(' || c == '{' || c == '[') {
stack.Push(c);
} else if (c == ')' && stack.Count > 0 && stack.Peek() == '(') {
stack.Pop();
} else if (c == '}' && stack.Count > 0 && stack.Peek() == '{') {
stack.Pop();
} else if (c == ']' && stack.Count > 0 && stack.Peek() == '[') {
stack.Pop();
} else {
return false;
}
}
return stack.Count == 0;
}
static void Main() {
Console.WriteLine(IsValidBrackets("{[()]}")); // Output: True
Console.WriteLine(IsValidBrackets("{[}]")); // Output: False
}
}
Edge Cases to Consider
- Empty String: Always valid.
- No Brackets: Strings without brackets are valid.
- Nested Brackets: Proper handling ensures any depth of nesting is valid.
Why Stacks Are Ideal for This Problem
Stacks allow you to efficiently match brackets in the correct order, making them a perfect fit for this problem. They also simplify code for managing nested structures.
Conclusion
Learning to check if a string has properly closed brackets is a valuable skill, not just for interviews but also for real-world applications like parsing and code validation. Practice the provided implementations and experiment with optimizations to deepen your understanding.
FAQ Section
1. Why use stacks for bracket matching?
Stacks are ideal for this problem because they maintain the order of elements, allowing efficient addition and removal, which is crucial for managing nested structures.
2. Can this problem be solved without a stack?
Yes, while it can be solved using other methods, they are often less efficient or more complex to implement.
3. What are other similar interview problems?
Related problems include balanced parentheses, valid expressions, and XML/HTML validation challenges.
4. How to handle non-bracket characters in the string?
Non-bracket characters can be ignored during the validation process; focus solely on brackets.
5. What is the best way to practice this problem?
Utilize coding platforms like LeetCode, HackerRank, or Codeforces to tackle variations of the problem and explore different edge cases.
