欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

括号生成

程序员文章站 2022-04-11 09:56:20
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。示例:输入:n = 3输出:[  “((()))”, “(()())”,  “(())()”,  “()(())”,  “()()()”]解题思路:采用递归的思路,每个位置放置一个字符,可能是“(”,也可能是“)”,但是左右括号数量不允许超过 n, 右括号数量在放置的时候,不允许超过左括号数量。package com.alibaba.study.leetcode;import...

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

示例:

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

解题思路:

采用递归的思路,每个位置放置一个字符,可能是“(”,也可能是“)”,但是左右括号数量不允许超过 n, 右括号数量在放置的时候,不允许超过左括号数量。

package com.alibaba.study.leetcode;

import com.alibaba.fastjson.JSON;

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

/**
 * @Auther: wjj
 * @Date: 2020/12/11 14:21
 * @Description:
 */
public class LeetCode22 {

    private static List<String> resList = new ArrayList<>();

    public static void main(String[] args) {
        System.out.printf("结果:" + JSON.toJSONString(generateParenthesis(3)));
    }

    public static List<String> generateParenthesis(int n) {
        getValidatePatter("", 0, 0, 0, n);
        return resList;
    }

    /**
     * @param res 拼接后的字符串
     * @param left 左括号数量
     * @param right  右括号数量
     * @param len  已经拼接字符串的长度
     * @param count  需要拼接的括号个数
     */
    private static void getValidatePatter(String res, int left, int right, int len, int count){
        if(count * 2 == len){
            resList.add(res);
            return ;
        }
        if(left < count) {
            getValidatePatter(res + "(", left + 1, right, len + 1, count);
        }
        if(left > right && right < count){
            getValidatePatter(res + ")", left, right + 1, len + 1, count);
        }
    }
}

本文地址:https://blog.csdn.net/Faker_Wang/article/details/111035213

相关标签: LeetCode