题解 | 括号生成

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<>();
        //dfs_slow(res, n * 2, new LinkedList<>());
        dfs(res, new LinkedList<>(), n, 0, 0);
        return res;
    }

    //记录当前左右括号数量避免生成无效序列
    public void dfs(ArrayList<String> res, LinkedList<Character> cur, int n,
                    int left, int right ) {
        if (left == n && right == n) {
            StringBuilder sb = new StringBuilder(2 * n);
            for (char c : cur) sb.append(c);
            res.add(sb.toString());
        } else {
            if (left < n) {
                cur.add('(');
                dfs(res, cur, n, left + 1, right);
                cur.removeLast();
            }
            if (right < left) {
                cur.add(')');
                dfs(res, cur, n, left, right + 1);
                cur.removeLast();
            }
        }
    }

    //枚举所有情况再筛选
    public void dfs_slow(ArrayList<String> res, int n, LinkedList<Character> cur) {
        if (cur.size() == n) {
            //验证是否合法
            if (isValid(cur)) {
                StringBuilder sb = new StringBuilder();
                for (char c : cur) sb.append(c);
                res.add(sb.toString());
            }
        } else {
            cur.add('(');
            dfs_slow(res, n, cur);
            cur.remove(cur.size() - 1);
            cur.add(')');
            dfs_slow(res, n, cur);
            cur.remove(cur.size() - 1);
        }
    }

    private boolean isValid(LinkedList<Character> cur) {
        // TODO
        Stack<Character> stack = new Stack<>();
        for (char c : cur) {
            if (stack.isEmpty() || c == '(') stack.add(c);
            else if (c == ')' && stack.peek() == '(') stack.pop();
        }
        return stack.isEmpty();
    }
}