leetcode|中等:22. 括号生成

jupiter
2022-04-25 / 0 评论 / 526 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年04月25日,已超过725天没有更新,若内容或图片失效,请留言反馈。

1.题目

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8

2. 题解

2.1 思路分析

思路1:DFS 比较简单 直接看代码

2.2 代码实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public void dfs(char[] brackets,int lNum,int rNum,int n,List<String> res){
        if(lNum==n && rNum==n) {
            res.add(new String(brackets));
            return;
        }

        // 增加左括号
        if(lNum<n){
            brackets[lNum+rNum] = '(';
            dfs(brackets,lNum+1,rNum,n,res);
        }
        // 增加右括号
        if(lNum>rNum&&rNum<n){
            brackets[lNum+rNum] = ')';
            dfs(brackets,lNum,rNum+1,n,res);
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] brackets = new char[2*n];
        dfs(brackets,0,0,n,res);
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int in = 3;
        System.out.println(solution.generateParenthesis(in));
    }
}

2.3 提交结果

提交结果执行用时内存消耗语言提交时间备注
通过0 ms41.3 MBJava2022/04/25 20:33添加备注

参考资料

  1. https://leetcode-cn.com/problems/generate-parentheses/
0

评论 (0)

打卡
取消