Editorial: Valid Parentheses

1 Intuition

Parentheses matching is a classic stack problem. When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check if the top of the stack has the matching opening bracket. Key insight: Use a stack (LIFO - Last In First Out) to track opening brackets and verify they match closing brackets in the correct order.

2 Approach

1. Create a stack and a mapping of closing to opening brackets 2. Iterate through each character: - If it's an opening bracket, push it to the stack - If it's a closing bracket: - Check if stack is empty (invalid) - Check if top of stack matches the opening bracket - Pop from stack if match 3. At the end, stack should be empty for valid string

3 Complexity Analysis

**Time Complexity:** O(n) - single pass through string **Space Complexity:** O(n) - stack stores at most n/2 opening brackets The solution is efficient and handles all edge cases.

4 Solution Code

def isValid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs:  # closing bracket
            if not stack or stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:  # opening bracket
            stack.append(char)
    return len(stack) == 0

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

5 Code Walkthrough

For s = "()[]{}": - Push '(' - stack: ['('] - See ')' - matches top, pop - stack: [] - Push '[' - stack: ['['] - See ']' - matches top, pop - stack: [] - Push '{' - stack: ['{'] - See '}' - matches top, pop - stack: [] - Stack empty = valid!