Fresher · Stacks & queues

Valid Parentheses

Given a string containing only (), {}, and [], determine whether every opening bracket is closed in the correct order. The empty string is valid.

Examples

s = "()[]{}" → true

s = "([)]" → false

Compare approaches

Repeated reduction

Repeatedly remove matched adjacent pairs until no changes remain.

Time: O(n²) · Space: O(n)

function isValid(s) {
  let before;
  do {
    before = s;
    s = s.replace(/\(\)|\[\]|\{\}/g, "");
  } while (before !== s);
  return s.length === 0;
}

Stack

A stack matches each closing bracket with the latest opening bracket.

Time: O(n) · Space: O(n)

function isValid(s) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };
  for (const c of s) {
    if ("([{ ".trim().includes(c)) stack.push(c);
    else if (stack.pop() !== pairs[c]) return false;
  }
  return stack.length === 0;
}

Common traps

Reject a closing bracket when the stack is empty.
A non-empty stack at the end is invalid.

Practise in the workspace →