Balanced Parenthesis problem

Easy

Problem

The string contains only the brackets ( ) { } [ ]. Return true if every opening bracket is closed by the same type of bracket, in the correct order.

Example 1

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

Example 2

Input:  "([)]"
Output: false

The ( is closed by ] before its own ).

Also asked as: valid parentheses

Test cases

Case 1

Input:    "()[]{}"
Expected: true

Case 2

Input:    "(]"
Expected: false

Case 3

Input:    "([)]"
Expected: false

Case 4

Input:    "{[]}"
Expected: true

Case 5

Input:    "("
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Stack

Time O(n)Space O(n)

Push openers; on a closer, the stack top must be its matching opener.

function isValid(s) {
const pair = { ')': '(', ']': '[', '}': '{' };
const st = [];
for (const c of s) {
if (c === '(' || c === '[' || c === '{') st.push(c);
else if (st.pop() !== pair[c]) return false;
}
return st.length === 0;
}