Skip to content

Valid Parentheses

question

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. Every close bracket has a corresponding open bracket of the same type.

idea

  • use a stack to store the open brackets, and when we encounter a close bracket, we check if it matches the top of the stack.
  • if it matches, we pop the top of the stack. If it doesn't match, we return False.
  • if the stack is empty at the end, we return True. Otherwise, we return False.

corner cases

  • if the string is empty, we return True.

code

def isValid(self, s: str) -> bool:
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else "#"
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

```typescript
function isValid(s: string): boolean {
    const stack: string[] = [];
    const mapping: { [key: string]: string } = { ")": "(", "}": "{", "]": "[" };
    for (const char of s) {
        if (char in mapping) {
            const topElement = stack.length > 0 ? stack.pop() : "#";
            if (mapping[char] !== topElement) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    return stack.length === 0;
}
```

what is wrong with this code?

#include <stack>
#include <iostream>

class Solution {
public:
    bool isValid(string s) {
        std::stack<char> stack;
        for (char c : s) {
            if (stack.empty()) stack.push(c);
            char prev = stack.top();
            switch(prev) {
                case '(':
                    if (c == ')') {
                        stack.pop();
                        continue;
                    }
                    break;
                case '[':
                    if (c == ']') {
                        stack.pop();
                        continue;
                    }
                    break;
                case '{':
                    if (c == '}') {
                        stack.pop();
                        continue;
                    }
                    break;
                default:
                    break;
            }
            stack.push(c);
        }
        return stack.empty();
    }
};

there are some major problems:

  1. when start, the stack is []
  2. it is empty, so we push the first char into stack ['(']
  3. then, we push it again after switch statement, so we have ['(', '(']
  4. this is wrong

You are switching on the previous character (top), but the standard logic is to switch on the current character (c).

If c is an Opener ((, [, {): You just push it. You don't need to check what was before it.

If c is a Closer (), ], }): You check if it matches the top.

#include <stack>
#include <string>

bool isValid(std::string s) {
    std::stack<char> stack;

    for (char c : s) {
        // 1. If it's an opening bracket, push it immediately
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } 
        // 2. If it's a closing bracket, we must check the stack
        else {
            // Case A: Stack is empty (e.g., input "]") -> Invalid
            if (stack.empty()) return false;

            char top = stack.top();

            // Case B: Check for mismatch
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }

            // Case C: It matches! Remove the pair.
            stack.pop();
        }
    }

    // 3. Final Check: Stack must be empty (all opened pairs were closed)
    return stack.empty();
}