Valid Parentheses

easy string stack

Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

Example 1

Input"({[]})"

Outputtrue

Every opener is closed by its matching kind in the right order.

Example 2

Input"([)]"

Outputfalse

'(' and '[' interleave instead of nesting properly.

brackets (only ( ) [ ] { })

def is_valid(s):
    match = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack.pop() != match[ch]:
                return False
    return not stack

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

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

bool isValid(string s) {
    unordered_map<char, char> match = {{')', '('}, {']', '['}, {'}', '{'}};
    stack<char> st;
    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);
        } else {
            if (st.empty() || st.top() != match[ch]) return false;
            st.pop();
        }
    }
    return st.empty();
}

Explanation

The key insight is that the most recently opened bracket must be the first one to close. That "last in, first out" behaviour is exactly what a stack gives us.

We walk through the string one character at a time. Every time we see an opening bracket (, [ or {, we push it onto the stack.

When we see a closing bracket, we look at the top of the stack. If it is the matching opener, great — we pop it off and keep going. If it does not match (or the stack is empty), the string is invalid and we return false.

At the very end the stack must be empty. Leftover openers mean some bracket was never closed, so that is also invalid.

Example: ({[]}) pushes (, {, [, then each closer matches the latest opener in turn, leaving an empty stack → valid.

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