题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例1

  1. 输入: "{[]}"
  2. 输出: true

示例2

输入: "([)]"
输出: false

实现

思路1 栈

此题可以通过维护一个栈来解决：
首先遍历字符串，

  • 如果是左括号则直接加入栈顶
  • 如果是右括号则pop栈顶的左括号与其匹配，此时如果两个括号不匹配，或者栈中为空，那么返回False。

全部遍历结束后，若栈为空，则匹配成功；若栈不为空，则匹配失败。
同时为了快速判断括号的类型，可以使用HashMap存储每种括号（key为右括号，值为对应的左括号），以便快速匹配。

这里复习一下cpp的数据结构的用法，如果是python的话stack使用list，HashMap用dict即可。

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        // 如果长度奇数，肯定无法匹配
        if (n%2==1) {
            return false;
        }

        stack<char> stk; //维护一个栈
        unordered_map<char,char> pairs = {
            {')','('},
            {']','['},
            {'}','{'}
        };
        for (char c: s){
            // 如果为右括号
            if(pairs.count(c)) {
                // 如果栈为空 或 括号不匹配
                if(stk.empty() || stk.top() != pairs[c]) {
                    return false;
                } else {
                    stk.pop();
                }
            } else{
                stk.push(c);
            }
        }
        // 遍历结束后，若栈为空则匹配成功
        // 若栈不为空则失败
        return stk.empty(); 
    }
};