20. Valid Parentheses，验证括号的合法性

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

class Solution:

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

    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in Solution.pd:
                stack.append(c)
            else:
                if (len(stack)==0
                        or Solution.pd[stack.pop()]!=c):
                    return False
        return stack == []

static unordered_map<char,char> \
_pmap {{'(',')'},{'{','}'},{'[',']'}};

class Solution {
public:
    bool isValid(string s) {
        vector<char> stack;
        stack.reserve(64);
        for(auto c: s){
            if(_pmap.contains(c))
                stack.push_back(c);
            else{
                if(stack.size()==0
                        || _pmap[stack.back()]!=c)
                    return false;
                stack.pop_back();
            }
        }
        return stack.size() == 0;
    }
};

struct stack{
    char *p;
    size_t size;
    size_t cap;
};

static char _counterpart(char c){
    switch(c){
    case '(':
        return ')';
    case '[':
        return ']';
    case '{':
        return '}';
    default:
        return '!';
    }
}

bool isValid(char * s){
    struct stack m = {};
    m.p = malloc(64);
    m.cap = 64;

    while(*s){
        if(*s=='(' || *s=='[' || *s=='{'){
            if(m.size == m.cap){
                m.p = realloc(m.p, m.cap+64);
                m.cap += 64;
            }
            m.p[m.size++] = *s;
        }
        else{
            if(m.size==0 || _counterpart(m.p[m.size-1])!=*s){
                free(m.p);
                return false;
            }
            --m.size;
        }
        ++s;
    }

    free(m.p);
    return m.size == 0;
}