Valid parentheses

Easy TimeO(n) SpaceO(n)

A string s of round, square and curly brackets is valid when every bracket is closed by one of the same kind and in the right order — "{[()]}" is valid, "([)]" is not, because the pairs cross. Given such a string, return true when it is valid. Anything left open at the end makes it invalid, as does a closer with nothing to close.

Examples

Example 1

Input
s = "{[()]}"
Output
true
Every bracket closes with its own kind, innermost pair first.

Example 2

Input
s = "([)]"
Output
false
The ) arrives while the [ is still open, so the two pairs cross.

The Code

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}
isValid("{[()]}");
Done
Step through isValid("{[()]}") call by call

More like this

All stacks & queues examples (8) →