题目内容

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

有效字符串需满足：

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

示例

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

示例 4：

输入：s = “([)]”
输出：false

示例 5：

输入：s = “{[]}”
输出：true

提示

1 <= s.length <= $10^4$
s 仅由括号 ‘()[]{}’ 组成

题解

求解匹配问题，一般需要用到一种特殊的数据结构，那就是栈。栈的特性是先进后出，在括号匹配问题上，同样符合这个性质，也就是，后面的左括号要率先被匹配掉，不然不符合规则。因此，我们有如下思考：

1、我们要利用栈，将左括号压入栈中。右括号用于在字符串遍历到时，和当前栈顶的元素进行匹配。如果匹配成功，则将栈顶元素弹出，继续匹配；如果匹配不成功，则直接返回false

2、在将字符串遍历完之后，要记得查看栈中是否还有元素，如果有，说明存在左括号没有右括号匹配的情况，此时也需要返回false

3、在编码技巧上，由于 ‘{‘ 和 ‘}’ 以及 ‘(‘ 和 ‘)’ 的ASCII码值差1， ‘[‘ 和 ‘]’ 的ASCII码值相差2，因此还可以通过这个特性简化代码。即判断差值是否小于等于2即可。因为，如果是不同类型的括号，差值一定大于2，相同类型的括号，差值一定在2以内。

代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(auto c: s){
            if(c == '(' || c == '[' || c == '{'){
                stk.push(c);
            }else{
                if(stk.size() && abs(stk.top() - c) <= 2) stk.pop();//根据ascii码来进行判断。如果匹配，差值一定小于等于2
                else return false;
            }
            
        }
        if(stk.size()) return false;
        return true;
    }
};