20. Valid Parentheses

class Solution {
    public boolean isValid(String s) {
        if ((s.length() & 1) == 1) return false;
        char[] stack = new char[s.length()];
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {
                stack[++top] = c;
            } else {
                if (top < 0) return false;
                char open = stack[top--];
                if ((c == ')' && open != '(') ||
                    (c == '}' && open != '{') ||
                    (c == ']' && open != '[')) {
                    return false;
                }
            }
        }
        return top == -1;
    }
}

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False

        stack = []

        for c in s:
            if c in "({[":
                stack.append(c)
            else:
                if not stack:
                    return False

                open_bracket = stack.pop()

                if ((c == ')' and open_bracket != '(') or
                    (c == '}' and open_bracket != '{') or
                    (c == ']' and open_bracket != '[')):
                    return False

        return len(stack) == 0

class Solution {
public:
    bool isValid(string s) {
        if (s.length() % 2 == 1) return false;

        vector<char> stack;

        for (char c : s) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push_back(c);
            } else {
                if (stack.empty()) return false;

                char open = stack.back();
                stack.pop_back();

                if ((c == ')' && open != '(') ||
                    (c == '}' && open != '{') ||
                    (c == ']' && open != '[')) {
                    return false;
                }
            }
        }

        return stack.empty();
    }
};

var isValid = function(s) {
    if (s.length % 2 === 1) return false;

    const stack = [];

    for (const c of s) {
        if (c === '(' || c === '{' || c === '[') {
            stack.push(c);
        } else {
            if (stack.length === 0) return false;

            const open = stack.pop();

            if ((c === ')' && open !== '(') ||
                (c === '}' && open !== '{') ||
                (c === ']' && open !== '[')) {
                return false;
            }
        }
    }

    return stack.length === 0;
};