easyStackStrings
Balanced Brackets
Decide whether a string of brackets is balanced: every opening bracket closed by the same type, in the right order. The standard stack question in coding rounds.
By Deepak KumarTests checked by DeepakJavaScript or Python
Given a string s made only of the characters ()[]{}, return true if it is balanced and false otherwise.
A string is balanced when every opening bracket is closed by the same type of bracket, and brackets close in the reverse order they were opened. An empty string is balanced.
Examples
Example 1
Input: s = "([]{})"
Output: trueExample 2
Input: s = "([)]" Output: false Why: [ is closed by ) before it is closed by ]
Constraints
0 <= s.length <= 10^4scontains only()[]{}
Hints
Hint 1
The most recently opened bracket must be the first one closed. Which data structure gives you the most recent item first?
Hint 2
Push opening brackets; on a closing bracket, the top of the stack must be its partner. What should be left at the end?
Solution
Show the solution (try it yourself first)
Approach: a stack
Brackets close in the reverse order they opened, which is exactly last-in, first-out, so a stack fits. Push every opening bracket. For a closing bracket, pop the top: it must be the matching opener, otherwise the string is unbalanced. Two edge cases catch most wrong answers: a closing bracket when the stack is empty, such as ")(", and leftover openers at the end, such as "(((". The string is balanced only if the stack ends empty.
def is_balanced(s):
pair = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in pair:
if not stack or stack.pop() != pair[ch]:
return False
else:
stack.append(ch)
return not stackComplexity
Time O(n), one pass. Space O(n) in the worst case, when every character is an opener. A counter alone only works for a single bracket type, which is a common follow-up question.