Valid Parentheses

Examples

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

Each pair opens and closes cleanly, and none of the pairs overlap improperly.

Input: s = "(]"
Output: false

The opening '(' ends up closed by ']', which is the wrong type of bracket.

Input: s = "([)]"
Output: false

'(' opens, then '[' opens — but ')' shows up before '[' has been closed, closing things out of order.

Constraints

• 1 <= s.length <= 10^4

• s consists only of the characters '(', ')', '[', ']', '{', and '}'.

Approach

Because a closing bracket always has to match the most recently opened bracket that hasn't been closed yet, this is naturally a last-in, first-out problem — which is exactly what a stack is for.

Walk through the string one character at a time. Every time you see an opening bracket, push it onto the stack. Every time you see a closing bracket, check it against whatever is on top of the stack: if it matches the type of bracket, pop it off and keep going; if it doesn't match (or the stack is empty when you needed something to match), the string is invalid. At the very end, the string is only valid if the stack is completely empty — otherwise something opened but never closed.

Solutions

Brute Force — Repeatedly Remove Matched Pairs

Repeatedly find and remove any immediately-adjacent matched pair like "()", "[]", or "{}" from the string. If the string collapses all the way down to empty, it was valid. This mimics collapsing the innermost matched pairs one at a time, but it re-scans the string over and over.

function isValid(s) {
  let previous;
  do {
    previous = s;
    s = s.replace("()", "").replace("[]", "").replace("{}", "");
  } while (s !== previous);

  return s.length === 0;
}

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

Optimal — Stack

Push opening brackets onto a stack. When a closing bracket appears, pop the stack and check that it's the matching opening bracket. If it isn't (or there's nothing to pop), the string is invalid right away.

function isValid(s) {
  const stack = [];
  const pairs = { ")": "(", "]": "[", "}": "{" };

  for (const char of s) {
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
    } else {
      if (stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }

  return stack.length === 0;
}

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