Leetcode题解——22 括号生成
22.括号生成
题目
https://leetcode-cn.com/problems/generate-parentheses/
题解
首先我们需要明白的一点是，在此题中，动态规划的思想类似于数学归纳法，当知道所有 i<n 的情况时，我们可以通过某种算法算出="" i="n" 的情况。="" 本题最核心的思想是，考虑="" 时相比="" n-1="" 组括号增加的那一组括号的位置。<="" p="">
当我们清楚所有 i<n 时括号的可能生成排列后，对与="" i="n" 的情况，我们考虑整个括号排列中最左边的括号。="" 它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号="" "(="" )"，我们认为这一组是相比="" n-1="" 增加进来的括号。<="" p="">
那么，剩下 n-1 组括号有可能在哪呢？
【这里是重点，请着重理解】
剩下的括号要么在这一组新增的括号内部，要么在这一组新增括号的外部（右侧）。
既然知道了 i<n 的情况，那我们就可以对所有情况进行遍历：<="" p="">
"(" + 【i=p时所有括号的排列组合】 + ")" + 【i=q时所有括号的排列组合】
其中 p + q = n-1，且 p q 均为非负整数。（如下图所示）
事实上，当上述 p 从 0 取到 n-1，q 从 n-1 取到 0 后，所有情况就遍历完了。
注：上述遍历是没有重复情况出现的，即当 (p1,q1)≠(p2,q2) 时，按上述方式取的括号组合一定不同。
如果用数学公式表示的话就像是下面这样：
代码
class Solution {
public List<String> generateParenthesis(int n) {
List<List<String>> result = new ArrayList<>();
List<String> list0 = new ArrayList<>();
list0.add("");
result.add(list0);
List<String> list1 = new ArrayList<>();
list1.add("()");
result.add(list1);
for (int i = 2; i <= n; i++) {
List<String> temp = new ArrayList<>();
for (int j = 0; j < i; j++) {
List<String> str1 = result.get(j);
List<String> str2 = result.get(i - 1 - j);
for (String s1 : str1) {
for (String s2 : str2) {
String el = "(" + s1 + ")" + s2;
temp.add(el);
}
}
}
result.add(temp);
}
return result.get(n);
}
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-09-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录