括号生成
程序员文章站
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