题解 | #括号生成#
括号生成
https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca
典型回溯算法的一个模版套用 针对回溯算法,大部分算法均可采用两种模版去做 backtrack(params) { if(终止条件){ 收集结果集 return; } for(int i = 0/cur; i < n;i++) { 记录结果集 backtrack(params); // 回溯 结果集回溯 } } // 上面这个模版适用于对排列、组合等题型 但是对回溯算法还有另外一个经典的适用场景,比如子集问题,这类算法有一个共同点,就是对元素的使用条件有要求,不可以重复,且存在一定的剪枝过程。针对于这种特征,回溯的另外一种模版可以解决此类的问题 backtrack(params) { if(终止条件){ 收集结果集 return; } 记录结果集 backtrack(params); // 回溯 结果集回溯 // 在一些特殊情况下,可能还需要选择当前元素,因此可能会有再次dfs的过程 // backtrack(params); } 括号生产明显就是一个子集问题的一个衍生,在生成的括号中,可能存在非法的括号,因此需要将其排除,因此下列算法的check方法就是判断生成的字符是否符合规则 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return string字符串ArrayList */ public ArrayList<String> generateParenthesis (int n) { // write code here ArrayList<String> res = new ArrayList<String>(); backtrack(n, 0, 0 , new StringBuilder(), res); return res; } public void backtrack(int n, int open, int close, StringBuilder str, ArrayList<String> res) { if (2 * n == str.length()) { if(check(str.toString())) { res.add(str.toString()); } return; } if (open < n) { str.append("("); backtrack(n, open + 1, close, str, res); str.deleteCharAt(str.length() - 1); } if (close < n) { str.append(")"); backtrack(n, open , close + 1, str, res); str.deleteCharAt(str.length() - 1); } } public boolean check(String str) { Deque<Character> stack = new LinkedList<>(); for (char ch : str.toCharArray()) { if (ch == ')') { if (stack.isEmpty() || stack.pop() != '(') { return false; } } else { stack.push(ch); } } return stack.isEmpty(); } }