题目主要信息:

  • 给定一个只包含大中小左右括号的字符串,判断其中括号是否合法
  • 大中小括号的数学顺序与合法无关,只需要每种左括号在右边有相应匹配的右括号即可,不可交叉匹配,应该是括号嵌套

具体思路:

括号的匹配规则应该符合先进后出原理:最外层的括号即最早出现的左括号,也对应最晚出现的右括号,即先进后出,因此使用同样先进后出的栈。

  • step 1:创建辅助栈,遍历字符串。
  • step 2:每次遇到小括号的左括号、中括号的左括号、大括号的左括号,就将其对应的呦括号加入栈中,期待在后续遇到。
  • step 3:如果没有遇到左括号但是栈为空,说明直接遇到了右括号,不合法。
  • step 4:其他情况下,如果遇到右括号,刚好会与栈顶元素相同,弹出栈顶元素继续遍历。
  • step 5:理论上,只要括号是匹配的,栈中元素最后是为空的,因此检查栈是否为空即可最后判断是否合法。

具体过程可以参考如下图示:

alt

代码实现:

class Solution {
public:
    bool isValid(string s) {
        stack<char> st; //辅助栈
        for(int i = 0; i < s.length(); i++){ //遍历字符串
            if(s[i] == '(') //遇到左小括号
                st.push(')'); //期待遇到右小括号
            else if(s[i] == '[') //遇到左中括号
                st.push(']'); //期待遇到右中括号
            else if(s[i] == '{') //遇到左打括号
                st.push('}'); //期待遇到右打括号
            else if(st.empty()) //必须有左括号的情况下才能遇到右括号
                return false;
            else if(st.top() == s[i]) //右括号匹配则弹出
                st.pop();
        }
        return st.empty(); //栈中是否还有元素
    }
};

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为字符串长度,遍历整个字符串
  • 空间复杂度:O(n)O(n),最坏情况下栈空间中记录整个字符串长度的右括号