「每日LeetCode」一大波括号相关的题

本文最后更新于：2023年3月19日 晚上

Lt1021. 删除最外层的括号

1021. 删除最外层的括号

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
示例 1：

1
2
3
4
5
输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

1
2
3
4
5
输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

1
2
3
4
5
输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

提示：

  1. S.length <= 10000
  2. S[i] 为 "(" 或 ")"
  3. S 是一个有效括号字符串

思路

每次左右相等的时候其实就是删除括号的实机

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
 * @lc app=leetcode.cn id=1021 lang=javascript
 *
 * [1021] 删除最外层的括号
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function (s) {
  let left = 0,
    right = 0,
    prev = 0;
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    console.log(i);
    if (char === "(") left++;
    else right++;
    if (left === right) {
      s = s.slice(0, prev) + s.slice(prev + 1, i) + s.slice(i + 1);
      i -= 2;
      prev = i + 1;
    }
  }
  return s;
};
// @lc code=end

1614. 括号的最大嵌套深度

如果字符串满足以下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：

  • 字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
  • 字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
  • 字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。

类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：

  • depth("") = 0
  • depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
  • depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
  • depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串

例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。
给你一个 有效括号字符串 s，返回该字符串的_ _s 嵌套深度 。

示例 1：

1
2
3
输入：s = "(1+(2*3)+((8)/4))+1"
输出：3
解释：数字 8 在嵌套的 3 层括号中。

示例 2：

1
2
输入：s = "(1)+((2))+(((3)))"
输出：3

示例 3：

1
2
输入：s = "1+(2*3)/(2-1)"
输出：1

示例 4：

1
2
输入：s = "1"
输出：0

提示：

  • 1 <= s.length <= 100
  • s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
  • 题目数据保证括号表达式 s 是 有效的括号表达式

思路

因为是有效括号，所以不需要判断，当为右括号时，栈的 size 即为嵌套最深的深度，用一个 max 来记录即可。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} s
 * @return {number}
 */
var maxDepth = function (s) {
  const stack = [];
  let max = 0;
  for (const char of s) {
    if (char === ")") {
      max = Math.max(stack.length, max);
      stack.pop();
    } else if (char === "(") {
      stack.push(char);
    }
  }
  return max;
};

剑指 Offer II 085. 生成匹配的括号

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：
输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1 输出：[“()”]

提示：
●1 <= n <= 8

注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/

思路

dfs 回溯法，优先塞入左括号，之后再塞入右括号

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const res = [],
    temp = [];
  const visit = (left, right) => {
    if (temp.length === 2 * n) return res.push(temp.slice().join(""));
    if (left < n) {
      temp.push("(");
      visit(left + 1, right);
      temp.pop();
    }
    if (left > right && right < n) {
      temp.push(")");
      visit(left, right + 1);
      temp.pop();
    }
  };
  visit(0, 0);
  return res;
};
// @lc code=end

有效的括号

Category Difficulty Likes Dislikes
algorithms Easy (44.53%) 3588 -

Tags
Companies
airbnb | amazon | bloomberg | facebook | google | microsoft | twitter | zenefits
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

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

示例 1：
输入：s = “()” 输出：true
示例 2：
输入：s = “()[]{}” 输出：true
示例 3：
输入：s = “(]” 输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 ‘()[]{}’ 组成

Discussion | Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
 * @lc app=leetcode.cn id=20 lang=javascript
 *
 * [20] 有效的括号
 */

// @lc code=start
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const stack = [];
  for (const char of s) {
    switch (char) {
      case ")":
        if (stack[stack.length - 1] !== "(") return false;
        stack.pop();
        break;
      case "]":
        if (stack[stack.length - 1] !== "[") return false;
        stack.pop();
        break;
      case "}":
        if (stack[stack.length - 1] !== "{") return false;
        stack.pop();
        break;
      default:
        stack.push(char);
        break;
    }
  }
  return stack.length === 0;
};
// @lc code=end

使括号有效的最少添加

Category Difficulty Likes Dislikes
algorithms Medium (73.04%) 237 -

Tags
Companies
只有满足下面几点之一，括号字符串才是有效的：

  • 它是一个空字符串，或者
  • 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
  • 它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号

  • 例如，如果 s = “()))” ，你可以插入一个开始括号为 “(()))” 或结束括号为 “())))” 。

返回 _为使结果字符串 s 有效而必须添加的最少括号数_。

示例 1：
输入：s = “())” 输出：1
示例 2：
输入：s = “(((“ 输出：3

提示：

  • 1 <= s.length <= 1000
  • s 只包含 ‘(‘ 和 ‘)’ 字符。

Discussion | Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * @lc app=leetcode.cn id=921 lang=javascript
 *
 * [921] 使括号有效的最少添加
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var minAddToMakeValid = function (s) {
  let left = 0,
    right = 0;
  for (const char of s) {
    if (char === "(") left++;
    else {
      if (left > 0) left--;
      else right++;
    }
  }
  return left + right;
};
// @lc code=end