有效的括号

原题链接：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) {  stackleft;  unordered_mapright = {  {')','('},  {']','['},  {'}','{'}  };  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& 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:  vectorgenerateParenthesis(int n) {  vectorresult;  string current;  backtrack(result, current, 0, 0, n);  return result;  } };

运行结果

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：11.2 MB, 在所有 C++ 提交中击败了67.69%的用户

通过测试用例：8 / 8

好好学习，天天向上

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