Balanced Parenthesis problem
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: trueExample 2
Input: "([)]" Output: false
The ( is closed by ] before its own ).
Also asked as: valid parentheses
Test cases
Case 1
Input: "()[]{}"
Expected: trueCase 2
Input: "(]" Expected: false
Case 3
Input: "([)]" Expected: false
Case 4
Input: "{[]}"
Expected: trueCase 5
Input: "("
Expected: falseView 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;}