Valid Parentheses

EasyString Stack

Before a code editor reformats a snippet, it checks that the snippet's brackets are balanced. You receive only the brackets, as a string s made of the six characters (, ), [, ], { and }.

Return true if the brackets are balanced and false otherwise. They are balanced when all of the following hold:

each closing bracket has the same type as the most recent opening bracket that is still unclosed, and closes it,
no closing bracket shows up while nothing is open,
no opening bracket is still unclosed when the string ends.

Example 1

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

Explanation: The () and [] pairs close inside the braces, and the braces close last.

Example 2

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

Explanation: The ] arrives while ( is the most recent unclosed bracket, so the types do not match.

Example 3

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

Explanation: The second ( is closed, but the first one never is.

Constraints

s is between 1 and 10^4 characters long.
Only the characters ()[]{} appear in s.

💡 Hint 1

The most recently opened bracket must be the first one closed. Which data structure is last-in, first-out?

💡 Hint 2

At the end, anything still open means the string is invalid.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Push every opening bracket onto a stack. On a closing bracket, the stack must be non-empty and its top must be the matching opener, otherwise the string is invalid. After the scan the stack must be empty.

Time O(n)Space O(n)

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

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') { stack.push(c); continue; }
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
        }
        return stack.isEmpty();
    }
}

/**
 * @param {string} s
 * @return {boolean}
 */
function isValid(s) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit