Leetcode --- Generate Parentheses(Medium)
===
## Description
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
### Examples
* Ex1:
**Input:** n = 3
**Output:** ["((()))","(()())","(())()","()(())","()()()"]
* Ex2:
**Input:** n = 1
**Output:** ["()"]
### Constraint
* 1 <= n <= 8
## Solution
==DP(Dynamic Programming) solution:==
先找規則:設n=3,解會有6個位子
```
_ _ _ _ _ _
1 2 3 4 5 6
```
第1個位子一定為 =='('== 才能滿足well-formed
```
( _ _ _ _ _
1 2 3 4 5 6
```
第二個位子有兩個選擇
* case 1: ==')'==
```
( ) _ _ _ _
1 2 3 4 5 6
```
**可以發現左邊兩個自己一組(完全配對)了,從第三個位子又是新的開始,且是n-1的small problem,又n=2的解為2種.** **==(Key1)==**
* case 2: =='('==
```
( ( _ _ _ _
1 2 3 4 5 6
```
**可以發現'('剩下最後一個,而剩下的位子中{ '(' , ')' ,' )' , ')' }的排列組合可以有3種.==(Key2)==**
以上狀況再位子2的時候已經把所有可以發生的情形都計算了,
n=3的解為2+3 =5種.
==結論:== 兩種狀況下可以很快地找到固定前面一部份把剩下一部份的所有組合找出
* case 1:左右括號已經成對 (e.g. ( ( ) )_ _ _ _),前面成兩對,後面取n-2的解
* case 2:左括號已經擺放了n-1個,剩下位子只要把剩餘數量的右括號先放好,再把最後一個左括號插到每一個位子
透過以上找出的規則套在n=4試找出解:
==首先第一個位子==必定是 '('
```
( _ _ _ _ _ _ _
1 2 3 4 5 6 7 8
```
==考慮第二個位子:==
* case 1: ')'
```
( ) _ _ _ _ _ _
1 2 3 4 5 6 7 8
```
左邊成一對,右邊的組合為 n-1 =3 => **5種解 (此case已結束)**
* case 2: '('
```
( ( _ _ _ _ _ _
1 2 3 4 5 6 7 8
```
兩種方法都不成立,**必須繼續往下探 (此case未結束)**
==考慮第三個位子:==
* case 1: ')'
```
( ( ) _ _ _ _ _
1 2 3 4 5 6 7 8
```
雖有一組已被對但仍未完全配對,又左括號數量為2不等於n-1,仍是另個方法都不成立,**必須繼續往下探 (此case未結束)**
* case 2: '('
```
( ( ( _ _ _ _ _
1 2 3 4 5 6 7 8
```
左括號數量為3等於n-1,方法成立,右括號剩餘數量為4,放入的方法數為:4個右括號放好,左括號插進來 = **4種解 (此case已結束)**
==考慮第四個位子==
* case 1:')'
```
( ( ) ) _ _ _ _
1 2 3 4 5 6 7 8
```
為完全配對,配兩對,所以剩下為n-2的組合數 **=2種解 (此case已結束)**
* case 2:'('
```
( ( ) ( _ _ _ _
1 2 3 4 5 6 7 8
```
左括號數量為3=n-1,方法二成立,剩餘右括號數量為3,方法數為將3個右括號放好,再插左括號: **3種方法(此case已結束)**
所有case都結束即完成 :總方法數為5+4+2+3=14種
check : (Catalan Number) N=4 : 1/(4+1) * (8 * 7 * 6 * 5) / (4 * 3 * 2 * 1) = 14
### Code Implement
```java=
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
StringBuilder tmp =new StringBuilder("");
para op =new para();
//parentheses operations
// tmp = op.addLeft(tmp);
// System.out.println(tmp + op.getStackNum());
// tmp =op.addRig(tmp);
// System.out.println(tmp +op.getStackNum());
if(n==1)
{
ans.add("()");
return ans;
}
else if(n==2)
{
ans.add("()()");
ans.add("(())");
return ans;
}
else
{
fun(op.addLeft(tmp),op,ans,n);
}
return ans;
}
private void fun(StringBuilder tmp,para op,List<String> ans,int n)
{
// System.out.println("Fir: "+tmp.toString() );
boolean SP = smallerProblem(tmp,op,ans,n);
// System.out.println("Sec: " +tmp.toString() );
boolean ST = smallerTails(tmp,op,ans,n);
// System.out.println("Thir: " +tmp.toString() );
//System.out.println(tmp.toString() + op.getStackNum() + SP + ST + n);
if(!SP && !ST)
{
String ex = tmp.toString();
int LP = op.getLeftParNum();
int RP = op.getRigParNum();
fun(op.addLeft(tmp),op,ans,n);
tmp = tmp.delete(0,tmp.length());
tmp = tmp.append(ex);
op.SetLefParNum(LP);
op.SetRigParNum(RP);
fun(op.addRig(tmp),op,ans,n);
}
if(!SP && ST)
fun(op.addRig(tmp),op,ans,n);
if(SP && !ST)
fun(op.addLeft(tmp),op,ans,n);
return ;
}
private boolean smallerProblem(StringBuilder tmp,para op,List<String> ans,int n)
{
tmp = op.addRig(tmp);
if(op.getStackNum() == 0)
{
List<String> preAns = generateParenthesis(n-op.getLeftParNum());
for(String ele : preAns)
{
String box = tmp.toString();
box = box.concat(ele);
ans.add(box);
}
return true;
}
return false;
}
private boolean smallerTails(StringBuilder tmp,para op,List<String> ans,int n)
{
tmp = op.delRig(tmp);
tmp = op.addLeft(tmp);
if(n-1 == op.getLeftParNum())
{
int RightRemain = n- op.getRigParNum();
int i=0;
while(i<RightRemain)
{
String box =tmp.toString();
for(int k =0;k<i;k++)
box = box.concat(")");
box =box.concat("(");
for(int k=0;k<RightRemain-i;k++)
box = box.concat(")");
ans.add(box);
i++;
}
tmp = op.delLef(tmp);
return true;
}
tmp = op.delLef(tmp);
return false;
}
}
class para
{
private int LparNum =0;
private int RparNum =0;
public StringBuilder addLeft(StringBuilder s)
{
s= s.append("(");
LparNum++;
return s;
}
public StringBuilder addRig(StringBuilder s)
{
s= s.append(")");
RparNum++;
return s;
}
public StringBuilder delRig(StringBuilder s)
{
s =s.deleteCharAt(s.length()-1);
RparNum--;
return s;
}
public StringBuilder delLef(StringBuilder s)
{
s =s.deleteCharAt(s.length()-1);
LparNum--;
return s;
}
public int getStackNum()
{
return this.LparNum - this.RparNum;
}
public int getLeftParNum()
{
return this.LparNum;
}
public int getRigParNum()
{
return this.RparNum;
}
public void SetLefParNum(int foo)
{
this.LparNum = foo;
}
public void SetRigParNum(int foo)
{
this.RparNum = foo;
}
}
```
* para物件提供字串**增加左括號或右括號**,並且每次增加都會記錄當前有多少數量,也提供另一個method,getStackNum(),來取得目前左右括號是否完全配對.
* 字串使用StringBuilder傳遞,因為想要達到call by reference的效果(仍是call by value),若是String做傳遞為call by value
* n=1 與 n=2 為初始條件 直接輸出
* smallerProblem():為上述之方法一,判斷是否完全配對,且將所有答案輸出
* smallerTails():為上述之方法二,判斷是否左括號數量為n-1,將剩下全補齊,把答案全輸出.
line 39~60: 判斷為哪一種case,加右括號完全配對?,加左括號餘補齊?,或是兩種都不成立,其中若兩種都不成立需要往下跑兩種case,須注意要把輸入還原(輸入字串tmp,左右括號的數量).
### Submission on Leetcode
Runtime: **2 ms, faster than 27.90%** of Java online submissions for Generate Parentheses.
Memory Usage: **38.9 MB, less than 76.23%** of Java online submissions for Generate Parentheses.
### Complexity Analysis
Worse case:兩個簡化方法都不成立,必須一直往下探:
=> O(2^n^)
###### tags: `Leetcode` `Medium` `DP` `Parentheses`
Sign in with Wallet
Connect another wallet