20. Valid Parentheses

stack O(n) time O(n) space

d = {')': '(', '}': '{', ']': '['}

class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        for c in s:
            if c in d:
                if not stk or d[c] != stk[-1]:
                    return False
                else:
                    stk.pop()
            else:
                stk += c # 注意这里c是一个字符所以可以用+=
        return not stk

unordered_map<char, char> m = {{')', '('}, {'}', '{'}, {']', '['}};
class Solution {
public:
    bool isValid(string s) {
        string stk;
        for (char c : s) {
            if (m.count(c)) {
                if (!stk.empty() && stk.back() == m[c]) {
                    stk.pop_back();
                } else return false;
            } else {
                stk += c;
            }
        }
        return stk.empty();
    }
};

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> hm{{')', '('}, {'}', '{'}, {']', '['}};
        stack<char> stk;
        for (auto c : s) {
            if (hm.count(c)) {
                if (stk.empty() || stk.top() != hm[c]) return false;
                stk.pop();
            } else {
                stk.push(c);
            }
        }
        return stk.empty(); // 注意最后要判空
    }
};