Solutions

1. Stack

O(n) time | O(n) space

Intuition

We can keep the opening brackets on a stack. Once we see a closing bracket, we pop the bracket on top of the stack if it matches.

At the end the stack should be empty if the string is valid.

Algorithm

Create an empty stack.
Iterate through the string from the first character to the last character.
- If the character is an opening bracket, push it onto the stack.
- Otherwise return false when the stack is empty or the bracket on top of it does not match, and pop that bracket in all other cases.
Return true if the stack is empty when the loop finishes.

{

[

(

)

]

}

push {

1 / 7

Code

def isValid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]:
                return False
        else:
            stack.append(c)
    return not stack

/**
 * @param {string} s
 * @returns {boolean}
 */
var isValid = function (s) {
  const pairs = { ')': '(', ']': '[', '}': '{' }
  const stack = []
  for (const c of s) {
    if (c in pairs) {
      if (stack.pop() !== pairs[c]) return false
    } else {
      stack.push(c)
    }
  }
  return stack.length === 0
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

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