括号合集

856. 括号的分数

给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：

• () 得 1 分。
• AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
• (A) 得 2 * A 分，其中 A 是平衡括号字符串。

示例 1：

输入： "()"
输出： 1

示例 2：

输入： "(())"
输出： 2

示例 3：

输入： "()()"
输出： 2

示例 4：

输入： "(()(()))"
输出： 6

提示：

1. S 是平衡括号字符串，且只含有 ( 和 ) 。
2. 2 <= S.length <= 50

C++

• DFS

class Solution {
public:
    int i = 0;
    // int res = 0; 要将res 写在函数内部，因为每次从‘（’开始这轮迭代时，内层结果都从0开始累加
    int scoreOfParentheses(string s) {
        if(s.size() == 2) return 1;
        return dfs(s);
    }

    int dfs(string s){
        int res = 0;
        while(i < s.size() && s[i] == '('){
            if(s[++i] == ')') res += 1;  // ++i 跳过当前 ‘（’
            else res += 2 * dfs(s);
            ++i; // ++i 跳过当前 ’）‘或 ’（‘
        }
        return res;
    }
};

• 只找最里层的（）

我们通过观察发现，() 是唯一贡献分数的结构，外括号只是为该结构添加了一些乘数。所以我们只需要关心 ()。

我们用 dd 维护当前括号的深度，对于每个 (，我们将深度加一，对于每个 )，我们将深度减一。当我们遇到 () 时，我们将 2^d加到答案中。

我们举个实际的例子，以 (()(())) 为例，我们首先找到内部两个闭合括号 ()，然后将分数加上对应的 2^d。实际上，我们是在计算 (()) + ((())) 的分数。

( ( ) ( ( ) ) )
  ^ ^   ^ ^

( ( ) ) + ( ( ( ) ) )
  ^ ^         ^ ^ 

class Solution {
public:
    int scoreOfParentheses(string s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                ++d;
            } else {
                --d;
                if (s[i - 1] == '(') {
                    ans += 1 << d;
                }
            }
        }
        return ans;
    }
};

// 作者：lcbin
// 链接：https://leetcode.cn/problems/score-of-parentheses/solution/by-lcbin-b9st/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

C++

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        dfs(res, "", 0, 0, n);
        return res; 
    }

    void dfs(vector<string>& res, string path,int l, int r, int n){ // l为左括号数， r为右括号数
        if(l < r  || l > n || r > n) return;
        if(l == r && l == n) res.push_back(path);
        dfs(res, path + '(', l + 1, r ,n); // 试试（
        dfs(res, path + ')', l, r + 1, n); // 试试 ）
    }
};

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 104
• s[i] 为 '(' 或 ')'

C++

class Solution {
public:
    // 有效的括号满足 1. 开头是左括号 && 左括号数 >= 右括号数  2.当左括号数 == 右括号数时,统计长度
    int res = 0;
    int longestValidParentheses(string s) {
        int n = s.size();
        for(int i = 0; i < n; i ++){
            if(s[i] == ')') continue;
            int l = 1;
            int r = 0;
            for(int L = 1; L < n - i; L ++){
                s[i + L] == '(' ? l ++ : r ++;
                if(l < r) break; // break语句只能跳出当前所在的最内层循环
                else if(l == r) res = max(res, L + 1);
            }
        }
        return res;
    }
};