题解 | #牛群的秘密通信#

知识点：

栈/字符串

分析：

两种方法：

一、利用一个栈来匹配括号，首先将 s[i] == '('|| s[i] == '{'|| s[i] == '['这些情况都一一压栈，在循环中，如果遇到了“ ) ] } ”,就和栈顶元素进行匹配，成功则继续，有一个不匹配，则整个字符串不匹配。若是循环中都判断结束了，那么最后还需要对栈是否为空进行判断，因为最后成对的括号都要弹出。

二、利用一个栈来匹配括号，但是这种方法的匹配与上面的方法不同，当出现 s[i] == '('|| s[i] == '{'|| s[i] == '['这些情况，将其对应的右半括号“ ) ] } ”压栈，在每一次循环中对当前字符进行判断，若是遍历到了当前栈为空或者是栈顶元素和当前元素不相等，则不是一个匹配的括号字符串，反之就弹出栈顶元素继续遍历。代码会更加简洁一些。

两个算法都是O(N)的时间复杂度

编程语言：

C++

完整代码：

第一种方法代码：

bool is_valid_cow_communication(string s) {
        stack<char> stk;
        for(int i = 0;i<s.length();i++){
            if(s[i] == '(' || s[i] == '{' || s[i] == '[') stk.push(s[i]);
            else{
                if(stk.empty()){
                    return false;
                }
                char curchar = stk.top();stk.pop();
                if(s[i] == '}' && curchar == '{'
                    ||s[i] == ']' && curchar == '['
                    ||s[i] == ')' && curchar == '(')continue;
                    else return false;
 
 
            }
        }
        if(stk.empty()) return true;else return false;
    }

第二种方法代码：

bool is_valid_cow_communication(string s) {
        stack<char> stk;
        for(int i = 0;i<s.length();i++){
            if(s[i] == '{') stk.push('}');
            else if(s[i] == '[') stk.push(']');
            else if(s[i] == '(') stk.push(')');
            else if(stk.empty() || stk.top() != s[i]){
                return false;
            }else stk.pop();
        }
        return true;
    }

第二种方法数组代替STL栈代码：

	char stk[100010];
    int tt = 0;
    bool is_valid_cow_communication(string s) {
        for(int i = 0;i<s.length();i++){
            if(s[i] == '{') stk[++tt] = '}';
            else if(s[i] == '[') stk[++tt] = ']';
            else if(s[i] == '(') stk[++tt] = ')';
            else if(tt <= 0 || stk[tt] != s[i]){
                return false;
            }else tt--;
        }
        return true;
    }