题目描述

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

有效字符串需满足：

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

样例

输入：s = "()"
输出：true

算法1

(模拟) $O(n)$

思路：从前往后开始模拟，如果是左括号的话，加入栈中，如果是右括号的话，则与当前的栈
看下是否匹配（根据栈的特性先进后出），所以当前栈里的元素一定是距离当前右括号最近的
那个左括号，然后依次匹配即可

C++ 代码

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for(auto c:s){
            if(c == '(' || c == '{' || c == '[')stk.push(c);
            else {
                if(stk.empty())return false;
                if(c == ')' && stk.top() == '(') stk.pop();
                else  if(c == '}' && stk.top() == '{') stk.pop();
                else  if(c == ']' && stk.top() == '[') stk.pop();
                else return false;
            }
        }
        return stk.empty();
    }
};

更好的阅读体验