Valid Parentheses

Problem

Given a string of brackets, determine if every opening bracket has a matching closing bracket in the correct order.

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

Input:  s = "(]"
Output: false

Python Solution

def is_valid_parentheses(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

C++ Solution

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

Java Solution

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

Complexity

Time: O(n) — each character triggers at most one push or pop. Space: O(n) — the stack can hold up to n unmatched opening brackets in the worst case.