ORIGIN

LeetCode 22. Generate Parentheses

ACM 1 mins281 words

Problem Description

https://leetcode.com/problems/generate-parentheses/

Analysis

Imagine we already have the all the well formed parentheses in 0 pairs to n-1 pairs. We can get the n pairs of parentheses by combining the x pairs with n-1-x pairs then combine with one pair “()”.

Why we have to separately consider the single brackets is because we can not just combine the x pairs and n-x pairs to make new well-formed parentheses. We may miss some situations.

We may not think of the well-formed n-1 pairs combine with one pair, but one pair combine with the n-1 pairs.

We can easily see that there is only three place to insert the n-1 pairs.

_1_(_2_)_3_ the first and third place are duplicate, we can just select the third place.

now what we do is to put our x pairs an n-x-1 pairs in to the blanks.

At first, 0 pair and 1 pair parentheses has only one combination: {""}, {"()"}, with this, we can get the 2 pairs parentheses and then all the way to n pairs.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<vector<string>> brackets = {{""}, {"()"}};
for(int i = 2; i <= n; i ++) {
vector<string> t;
for(int j = 0; j < i; j ++) {
for(auto k : brackets[j]) {
for(auto l : brackets[i - j - 1]) {
t.push_back("(" + k + ")" + l);
}
}
}
brackets.push_back(t);
}
return brackets[n];
}
};
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|