目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
數字 n 代表生成括號的對數，請你設計一個函式，用于能夠生成所有可能的并且 有效的 括號組合，
示例 1：
輸入：n = 3
輸出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
輸入：n = 1
輸出：["()"]
提示：
1 <= n <= 8
2、思路
(dfs) O ( C 2 n n ) O(C_{2n}^{n}) O(C2nn?)
首先我們需要知道一個結論，一個合法的括號序列需要滿足兩個條件：
- 1、左右括號數量相等
- 2、任意前綴中左括號數量
>=右括號數量 （也就是說每一個右括號總能找到相匹配的左括號）
題目要求我們生成n對的合法括號序列組合，可以考慮使用深度優先搜索，將搜索順序定義為列舉序列的每一位填什么，那么最終的答案一定是有n個左括號和n個右括號組成，
如何設計dfs搜索函式？
最關鍵的問題在于搜索序列的當前位時，是選擇填寫左括號，還是選擇填寫右括號 ？因為我們已經知道一個合法的括號序列，任意前綴中左括號數量一定 >= 右括號數量，因此，如果左括號數量不大于 n，我們就可以放一個左括號，來等待一個右括號來匹配 ，如果右括號數量小于左括號的數量，我們就可以放一個右括號，來使一個右括號和一個左括號相匹配，
遞回搜索樹如下：
遞回函式設計
void dfs(int n ,int lc, int rc ,string str)
n是括號對數，lc是左括號數量，rc是右括號數量，str是當前維護的合法括號序列，
搜索程序如下：
- 1、初始時定義序列的左括號數量
lc和右括號數量rc都為0， - 2、如果
lc < n，左括號的個數小于n，則在當前序列str后拼接左括號， - 3、如果
rc < n && lc > rc, 右括號的個數小于左括號的個數，則在當前序列str后拼接右括號， - 4、當
lc == n && rc == n時，將當前合法序列str加入答案陣列res中，
時間復雜度分析： 經典的卡特蘭數問題，因此時間復雜度為 O ( 1 n + 1 C 2 n n ) = O ( C 2 n n ) O(\frac{1}{n+1}C_{2n}^{n}) = O(C_{2n}^n) O(n+11?C2nn?)=O(C2nn?) ，
3、c++代碼
class Solution {
public:
vector<string> res; //記錄答案
vector<string> generateParenthesis(int n) {
dfs(n , 0 , 0, "");
return res;
}
void dfs(int n ,int lc, int rc ,string str)
{
if( lc == n && rc == n) res.push_back(str);
else
{
if(lc < n) dfs(n, lc + 1, rc, str + "(");
if(rc < n && lc > rc) dfs(n, lc, rc + 1, str + ")");
}
}
};
4、java代碼
class Solution {
static List<String> res = new ArrayList<String>(); //記錄答案
public List<String> generateParenthesis(int n) {
res.clear();
dfs(n, 0, 0, "");
return res;
}
public void dfs(int n ,int lc, int rc ,String str)
{
if( lc == n && rc == n) res.add(str);
else
{
if(lc < n) dfs(n, lc + 1, rc, str + "(");
if(rc < n && lc > rc) dfs(n, lc, rc + 1, str + ")");
}
}
}
原題鏈接： 22. 括號生成
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/293718.html
標籤：java
下一篇：cgb2106-day15