熊二 | C++ | #牛群的秘密通信#

题目考察的知识点

• 栈
• 括号匹配

题目解答方法的文字分析

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

分析完之后，代码其实就比较好写了，

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

本题解析所用的编程语言

• cpp

完整且正确的编程代码

class Solution {//switch 计划A 2022年8月19日10点45分-10点57分
public:
    bool is_valid_cow_communication(string s) {
        const int N = 1e5;
        char stk[N];
        int tt=-1;
        for(char x:s){
            switch(x){
                case '(':
                    stk[++tt]=')';break;
                case '[':
                    stk[++tt]=']';break;
                case '{':
                    stk[++tt]='}';break;
                default:
                    if(tt<0 || stk[tt]!=x)return false;
                    --tt;
            }
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，
        //说明有相应的左括号没有右括号来匹配，所以false，否则就true
        return tt<0;
    }
};

EOF