题目描述

给定一个只包括 '(',')','{','}','[',']'  的字符串 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();
    }
};

越努力越幸运