22 括号生成

/**
 * @description: 22 括号生成
 * @author: zyh
 * @create: 2021-01-13 20:55
 **/
public class GenerateParenthesis_22 {

    @Test
    public void tt(){
        List<String> list = generateParenthesis(3);
        list.forEach(item->{
            System.out.println(item);
        });
    }

    public List<String> generateParenthesis(int n) {
        n=n*2;
        List<String> list=new LinkedList<>();
        String s="";
        getThirdCode(list,n,s);
        return list;
    }

    private void getThirdCode(List<String> list, int n,String currCode) {
        if (currCode.length()<n){
            getThirdCode(list,n,currCode+"(");
            getThirdCode(list,n,currCode+")");
        }else {
            boolean res=check(currCode);
            if (res){
                list.add(currCode);
            }
        }
    }

    private boolean check(String currCode) {
        Stack<Character> stack=new Stack();
        for (Character c: currCode.toCharArray()) {
            if(stack.size()==0){
                if (c.equals(')')){
                    return false;
                }
                stack.push(c);
            }else if(c.equals(stack.peek())){
                stack.push(c);
            }else {
                stack.pop();
            }
        }
        return stack.size()==0;
    }
}
/**
 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 输入：n = 3
 输出：[
 "((()))",
 "(()())",
 "(())()",
 "()(())",
 "()()()"
 ]
*/