题解 | 有效括号序列

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isValid(string s) {
        stack<char> st;
        unordered_map<char, char> mapping = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };

        for (char c : s) {
            // 如果是闭括号
            if (mapping.find(c) != mapping.end()) {
                // 如果栈为空，用特殊字符表示
                char top_element = st.empty() ? '#' : st.top();

                // 如果栈顶元素不匹配当前闭括号对应的开括号
                if (top_element != mapping[c]) {
                    return false;
                }
                // 匹配成功，弹出栈顶元素
                st.pop();
            } else {
                // 如果是开括号，压入栈中
                st.push(c);
            }
        }

        // 最后检查栈是否为空
        return st.empty();
    }
};

为了解决这个问题，我们需要判断给定的括号字符串是否有效。有效的括号字符串必须满足以下条件：
每个开括号必须有对应的闭括号。
括号必须正确嵌套，即闭括号必须按顺序匹配最近的开括号。

方法思路
栈的使用：利用栈的后进先出（LIFO）特性来匹配括号。遍历字符串时，遇到开括号就压入栈中，遇到闭括号则检查栈顶元素是否与之匹配。
提前终止：如果遇到闭括号时栈为空或栈顶元素不匹配，可以立即返回false，因为这意味着括号不按正确顺序闭合。
最终检查：遍历完字符串后，如果栈为空，说明所有括号都正确匹配，返回true；否则返回false。

代码解释
初始化：创建一个空栈和一个字典mapping，用于存储闭括号到开括号的映射。
遍历字符：对于字符串中的每个字符：
如果是闭括号，检查栈顶元素是否匹配。若栈为空或栈顶元素不匹配，返回false。
如果是开括号，压入栈中。
最终检查：遍历结束后，栈为空则返回true，否则返回false。
这种方法确保在O(n)时间内解决问题，其中n是字符串的长度，空间复杂度为O(n)用于栈的存储。