有效的括号

原题链接：https://leetcode.cn/problems/valid-parentheses/

题目描述

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

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true

示例 2：

输入：s = “()[]{}”
输出：true

示例 3：

输入：s = “(]”
输出：false

栈容器

对于一个字符串，比如"([{}[)"，我们需要从一端开始读入数据，同时将新读入的数据和已有数据对比，判断是否符合条件，即左右括号是否对应。
如果相同，则弹出已经存储的对应字符。如果不同，则存储起来，将末尾元素用于下次对比。

1. 先读入'('，储存起来。
2. 然后读入'['，目前存储的最后一个元素是'('，判断不相等，继续循环。
3. 然后读入'{'，目前存储的最后一个元素是'['，判断不相等，继续循环。
4. 然后读入'}'，目前存储的最后一个元素是'{'，判断符合条件，弹出元素，继续循环。
5. 然后读入'['，目前存储的最后一个元素是'['，返回false。

我们每次需要存取的，只是容器的末尾元素，因此，我们使用栈容器存储读取到的字符。
每次判断是否符合条件，需要判断两个不同的量：左括号和右括号，为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。

上代码

代码中有一些需要注意的地方：

• 直接使用哈希表自带的统计方法判断是否存在，不存在时返回0，不执行if语句。
• 返回值为left.empty()，当遍历完后，容器中仍有元素残留，表面左括号和右括号未一一对应，不为空，返回0。

class Solution {
public:
    bool isValid(string s) {
        stack<char>left;
        unordered_map<char, char>right = {
            {')','('},
            {']','['},
            {'}','{'}
        };
        for (int i = 0; i < s.size(); i++)
        {
            if (right.count(s[i]))
            {
                if (left.empty() || left.top() != right[s[i]])
                {
                    return false;
                }
                left.pop();
            }
            else
                left.push(s[i]);
        }
        return left.empty();
    }
};

运行结果
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：6.1 MB, 在所有 C++ 提交中击败了75.89%的用户
通过测试用例：92 / 92

其他方法

❌使用循环抠掉中间

如果字符串符合条件，那么居中位置一定是"()"或"[]"或"{}"，将这部分抠去后的新字符串的中心位置，也一定是这几个字符串。
但如果字符串一侧也有"()"或"[]"或"{}"，如"{(){}[]}"则容易被误判，不建议使用

✔️双指针对比

由于输入类型是字符串，我们可以使用双指针的方法取值对比，比较简单，在此不放代码。

括号生成

原题链接：https://leetcode.cn/problems/generate-parentheses/

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

递归裁剪

递归比较考验思维，我们可以具几个简单的例子来理清代码思路。
如果n=2，我们使用穷举法，有两情况 ："(())"和"()()"。
显然，我们需要监控的量很多：左括号数量、右括号数量、结果字符串等，无法使用return一次性返回并接收。
因此，我们使用引用的方法，将结果字符串等相关变量声明在函数外，使用引用的方法读取或修改。
生成的括号是有效的，因此我们需要先插入左括号'('：

1. 结果字符串为"("。
2. 分两种情况，都需要执行：追加左括号'('或追加右括号')'。
3. 追加完左括号后，结果字符串为"(("，接下来递归分别追加两次右括号')'。
4. 回到第二步的第二种情况，追加完右括号后的结果字符串为"()"。
5. 重复第一步和第二步，得到结果字符串"()()"。

对于结束条件的判定

由于我们输入的是“生成括号的对数”，因此，输入n，结果字符串长度为2n（一对括号包含左右括号共两个字符）。
对于左括号，它追加的执行条件为count(left)<n。
对于右括号，当存在多余的左括号时就可以尝试追加，因此执行条件为count(right)<count(left)。
对于递归结束条件，即字符串达到题目允许的最大长度时返回，最大长度为2n。

上代码

class Solution {
    void backtrack(vector<string>& ans, string& cur, int left, int right, int n) {
        if (cur.size() == n * 2) {
            ans.push_back(cur);
            return;
        }
        if (left < n) {
            cur.push_back('(');
            backtrack(ans, cur, left + 1, right, n);
            cur.pop_back();
        }
        if (right < left) {
            cur.push_back(')');
            backtrack(ans, cur, left, right + 1, n);
            cur.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string current;
        backtrack(result, current, 0, 0, n);
        return result;
    }
};

运行结果
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：11.2 MB, 在所有 C++ 提交中击败了67.69%的用户
通过测试用例：8 / 8

好好学习，天天向上🚀

这次的比较简短，但挺费脑子的（对我这个萌新是这样的😢）。