leetcode 22 括号生成

22. 括号生成

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

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

暴力1思路

  • 给定n,所以合法的括号包含n个左括号和n个右括号。每次选择增加左/右,剩下的字符串与原问题相同
  • 左括号>n / 右括号 > n / 右括号 > 左括号 这些情况均不合法,用于剪枝
class Solution {
public:
    vector<string> res;
    
    vector<string> generateParenthesis(int n) {
        dfs(n, "", 0, 0);
        return res;
    }

    void dfs (int n, string cur, int lc, int rc) {
        if (lc > n || rc > n || rc > lc) {
            return;
        }
        if (lc == n && rc == n) {
            res.push_back(cur);
            return;
        }
        dfs(n, cur + "(", lc + 1, rc);
        dfs(n, cur + ")", lc, rc + 1);
    }
};

dp 思路

  • n的括号,可以由小于n的括号推导出
  • 从n-1到n,增加了一对括号。

    • 这一对括号要么在原有括号外侧;( 原来 )
    • 这一对括号要么在原有括号右侧;原来 ()
  • 也就是实际结果等于

    • ( i=p的括号 ) + i=q的括号
    • p+q = n-1
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) {
            return {};
        }
        if (n == 1) {
            return {"()"};
        }
        vector<vector<string>> dp(n+1); 
        dp[0] = {""};
        dp[1] = {"()"};
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                for (string p : dp[j]) {
                    for (string q : dp[i-j-1]) {
                        string cur = "(" + p + ")" + q;
                        dp[i].push_back(cur);
                    }
                }
            }
        }
        return dp[n];
    }
};

评论

暂无评论