~/leetcode $ 20. Valid-Parentheses

Back to another easy problem yippe. Classic problem here, we want to use a stack to keep track of the currently open parentheses.

If we find a open parentheses, we can append it to the stack. If we find a closed parentheses, there are 3 options:

1. if it matches the open parentheses at the top of the current stack, it is valid and the top of the stack is popped. Then we continue
2. if it does not match the open parentheses at the top of the current stack, the input string is invalid and we return false.
3. if the current stack is empty, the input string is also invalid.

class Solution {
public:
    bool isValid(string s) {
        vector<char> stack {};
        unordered_map<char, char> matching {
            {'}', '{'},
            {']', '['},
            {')', '('}
        };

        for (char c: s) {
            if (!matching.contains(c)) {
                // open
                stack.push_back(c);
            } else {
                // closed
                if (stack.empty() || stack.back() != matching[c]) {
                    return false;
                }
                stack.pop_back();
            }
        }

        return stack.empty();
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 7m 7s