力扣 20. 有效的括号

题目描述

力扣题目链接

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

有效字符串需满足：

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

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([)]"
输出：false

示例 5：
输入：s = "{[]}"
输出：true

---

题解

C++

采用栈处理，时间复杂度$O(n)$，空间复杂度取决于暂时无法匹配的括号的最大数目：

#include <iostream>
#include <stack>

using namespace std;

class Solution {
    
public:
    static bool isValid(string s) {
    
        stack<char> brackets_stack;

        for (char c: s) {
    
            if (c == '(' || c == '[' || c == '{') {
    
                brackets_stack.push(c);
            } else if (brackets_stack.empty()) {
    
                return false;
            } else if (c == ')') {
    
                if (brackets_stack.top() == '(') {
    
                    brackets_stack.pop();
                } else {
    
                    return false;
                }
            } else if (c == ']') {
    
                if (brackets_stack.top() == '[') {
    
                    brackets_stack.pop();
                } else {
    
                    return false;
                }
            } else if (c == '}') {
    
                if (brackets_stack.top() == '{') {
    
                    brackets_stack.pop();
                } else {
    
                    return false;
                }
            }
        }

        return brackets_stack.empty();
    }
};

int main() {
    
    cout << Solution::isValid("]") << endl;

    return 0;
}

在扫描到左括号的时候，可以直接入栈右括号，这样在扫描到右括号时就只需要和栈顶相比较就可以了，可以简化代码。

#include <iostream>
#include <stack>

using namespace std;

class Solution {
    
public:
    static bool isValid(string s) {
    
        stack<char> brackets_stack;

        for (char c: s) {
    
            if (c == '(') {
    
                brackets_stack.push(')');
            } else if (c == '[') {
    
                brackets_stack.push(']');
            } else if (c == '{') {
    
                brackets_stack.push('}');
            } else if (brackets_stack.empty() || brackets_stack.top() != c) {
    
                return false; // 栈空说明有右括号无法被匹配 栈顶不同说明括号不匹配
            } else {
    
                brackets_stack.pop(); // 匹配成功将栈顶出栈
            }
        }

        return brackets_stack.empty();
    }
};

int main() {
    
    cout << Solution::isValid("]") << endl;

    return 0;
}