建设银行门户网站,惠州公司网站建设价格,哈尔滨做网站企业,江宁网站建设哪家好题目描述
数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。
示例 1#xff1a; 输入#xff1a;n 3 输出#xff1a;[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2#xff1a; 输入…题目描述
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1 输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2 输入n 1 输出[“()”] 提示 1 n 8 思路
首先思考算法的暴力解法再对解法进行优化得到最终解法。 暴力思路 输入为n时输出的字符串长度为2n。可以定义一个长度为2n的数组每一个位置不是左括号就是右括号。暴力生成所有的长度为2n的字符串然后遍历所有的字符串一旦左括号数小于右括号数就判定为不合格的字符串。这种算法的时间复杂度为O(2^2n) 这种算法的时间复杂度太高根本没必要一下子生成这么多的字符串浪费时间。我们可以使用条件来对生成字符串的过程进行剪枝。
条件观察 输入为n时输出字符串长度为2n 局部字串符合条件的情况下右括号不会作为新串的开头如()‘合理但’)()不合理 局部串中 n 左括号数 右括号数 由条件分析 如果leftn则返回上一层 如果left right则返回上一层 代码
class Solution {public ListString generateParenthesis(int n) {ListString results new ArrayListString();gen(0, 0, n, , results);return results;}// 递归函数参数说明如下// left 左括号使用的个数// right右括号使用的个数// n输入的n用于判断左右括号是否超出限制// result当前生成的合格的子串// results合格字符串的列表public void gen(int left,int right,int n,String result, ListString results){if(left n right n){results.add(result);return;}// 两个剪枝条件只要满足剪枝条件则不再继续if(left n || left right)return;gen(left1, right, n, result(, results);gen(left, right1, n, result), results);}
}
