2. Valid Parentheses

Given a string s made only of the characters ()[]{}, decide whether it is valid:

every opening bracket is closed by a bracket of the same type,
brackets close in the correct order,
every closing bracket has a matching opening bracket.

Example 1

Input: s = "()"
Output: true

Example 2

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

Example 3

Input: s = "(]"
Output: false

Example 4

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

Explanation: The brackets are matched in count but closed in the wrong order.

Constraints

1 <= s.length <= 10^4
s consists only of ()[]{}

💡 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