LeetCode刷题Java版022.括号生成

作者：沉默王二
发布时间：2022-08-09T22:16:09.170+0800

022.括号生成

题意

请你设计一个方法，用于能够生成所有可能的具有n对括号并且 有效的 括号组合。

1 <= n <= 8

难度

中等

示例

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

分析

因为n的范围很小，所以我们直接考虑搜索。什么是搜索呢？

搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。想了解更多关于搜索的次条，戳https://oi-wiki.org/search/ 。

但是盲目的搜索只能使我们的复杂度直线上升，所以我们不妨先来思考， 有效括号 的组合到底有那些共通之处，我们挨个看，分别统计每个位置及其之前，共有多少个左括号和右括号，例如：

String: "( ( ( ) ) )"

位置 :1 2 3 4 5 6

左括号数量:1 2 3 3 3 3

右括号数量:0 0 0 1 2 3

String: "( ( ) ( ) )"

位置 :1 2 3 4 5 6

左括号数量:1 2 2 3 3 3

右括号数量:0 0 1 1 2 3

我们发现，无论在哪个位置，右括号数量都是小于等于左括号的，所以我们搜索的时候，只需要把握住这一点，就可以严格限制我们的搜索方向，使我们搜索出来的必然是 有效的 括号组合。

class Solution {

List res = new ArrayList<>();

void DFS(int numLef,int numRig,int numTot,String sta){

if(numRig == numTot){

res.add (sta);

return ;

}

if(numRig < numLef)

DFS(numLef,numRig + 1,numTot,sta + ")");

if(numLef < numTot)

DFS(numLef + 1,numRig,numTot,sta + "(");

}

public List generateParenthesis(int n) {

DFS(0,0,n,"");

return res;

}

上例中，我们定义了一个叫 DFS 的方法，这里简单解释一下 DFS。在搜索算法中，DFS（Depth First Search，深度优先搜索）常常指利用递归方便地实现暴力枚举的算法。以上的题解中我们就用到了递归。

n的范围很小，从 1 到 8，我们依次在本地输入1-8，然后把答案导出来，直接对8个结果 res 赋值，然后在测试的时候，题目需要哪个就返回哪个，例如我们可以把1、2、3、4、5、6、7、8的答案都分别存入了res[1]、res[2]、res[3]、res[4]、res[5]、res[6]、res[7]、res[8]，题目要我们返回任何一个答案，我们都能回答。虽然感觉上有点投机取巧，但是实际上，对于一些范围小，而正常搜索的时间消耗大的题型，这其实是一个正确的选择，并且高效。

总结

今天的题解中，我们先总结出了有效括号组合的共通之处——无论在哪个位置，右括号数量都是小于等于左括号的，从而写出了我们的搜索方法，而不是盲目生成个括号然后再去挨个遍历判断是否合法，以及根据了n的范围极小这个特性，提出了打表的方法，从而使得性能进一步提升。

力扣链接：https://leetcode.cn/problems/generate-parentheses/

022.括号生成

题意

请你设计一个方法，用于能够生成所有可能的具有n对括号并且 有效的 括号组合。

1 <= n <= 8

难度

中等

示例

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

分析

因为n的范围很小，所以我们直接考虑搜索。什么是搜索呢？

String: "( ( ( ) ) )"

位置 :1 2 3 4 5 6

左括号数量:1 2 3 3 3 3

右括号数量:0 0 0 1 2 3

String: "( ( ) ( ) )"

位置 :1 2 3 4 5 6

左括号数量:1 2 2 3 3 3

右括号数量:0 0 1 1 2 3

class Solution {

List res = new ArrayList<>();

void DFS(int numLef,int numRig,int numTot,String sta){

if(numRig == numTot){

res.add (sta);

return ;

}

if(numRig < numLef)

DFS(numLef,numRig + 1,numTot,sta + ")");

if(numLef < numTot)

DFS(numLef + 1,numRig,numTot,sta + "(");

}

public List generateParenthesis(int n) {

DFS(0,0,n,"");

return res;

}

总结

力扣链接：https://leetcode.cn/problems/generate-parentheses/

022.括号生成

题意

请你设计一个方法，用于能够生成所有可能的具有n对括号并且 有效的 括号组合。

1 <= n <= 8

难度

中等

示例

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

分析

因为n的范围很小，所以我们直接考虑搜索。什么是搜索呢？

String: "( ( ( ) ) )"

位置 :1 2 3 4 5 6

左括号数量:1 2 3 3 3 3

右括号数量:0 0 0 1 2 3

String: "( ( ) ( ) )"

位置 :1 2 3 4 5 6

左括号数量:1 2 2 3 3 3

右括号数量:0 0 1 1 2 3

class Solution {

List res = new ArrayList<>();

void DFS(int numLef,int numRig,int numTot,String sta){

if(numRig == numTot){

res.add (sta);

return ;

}

if(numRig < numLef)

DFS(numLef,numRig + 1,numTot,sta + ")");

if(numLef < numTot)

DFS(numLef + 1,numRig,numTot,sta + "(");

}

public List generateParenthesis(int n) {

DFS(0,0,n,"");

return res;

}

总结

力扣链接：https://leetcode.cn/problems/generate-parentheses/

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412