DFS + 回溯法解决字符串生成问题
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
思路:
这是字符串生成的问题,可以考虑 DFS + 回溯法。
我们利用 DFS 递归地遍历当前下一位所有可能的括号组合(当前至多有 2 种选择),然后用回溯法回到递归前的状态,当左右括号数等于所需的对数时,即收集结果。如此我们可以遍历每一位的括号组合。
细节:「剪枝」,即进行下一步之前,通过条件判断过滤掉一些不可能的选择,比如,右括号不能多于左括号,所以当左右括号数相等时,我们下一步只能添加左括号;否则,我们既可以添加左括号,也可右括号,依次回溯遍历即可。
时间复杂度:O(4^n/n^0.5)
空间复杂度:O(n)
实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| class Solution { public List<String> generateParenthesis(int n) { int l = 0, r = 0; sb = new StringBuilder(); ret = new LinkedList<>(); helper(l, r, n); return ret; } private StringBuilder sb; private List<String> ret; private void helper(int l, int r, int n) { if (l > r && l < n) { for (int i = 0; i < 2; i++) { if (i == 0) { sb.append('('); helper(l + 1, r, n); sb.deleteCharAt(sb.length() - 1); } else { sb.append(')'); helper(l, r + 1, n); sb.deleteCharAt(sb.length() - 1); } } } else if (l == r && l < n) { sb.append('('); helper(l + 1, r, n); sb.deleteCharAt(sb.length() - 1); } else { for (int i = 0; i < n - r; i++) { sb.append(')'); } ret.add(sb.toString()); sb.delete(sb.length() - n + r, sb.length()); } } }
|