impl Solution {
    pub fn is_valid(s: String) -> bool {
        let is_match = |p, q| {
            p == '(' && q == ')' || p == '[' && q == ']' || p == '{' && q == '}'
        };
        let mut stk = vec![];
        for c in s.chars() {
            match stk.last() {
                Some(last) => {
                    if is_match(*last, c) {
                        stk.pop();
                    } else {
                        stk.push(c);
                    }
                }
                None => stk.push(c)
            }
        }
        return stk.is_empty();
    }
}