Generate Parentheses

捕获3.PNG

看到题目第一个想到的解法是dp,那么就要找规律了
n=1 result : ()
n=2 result : (()),()()
n=3 result : ((())),(()()),()(()),(())(),()()()
那么规律就是每一次都比上一个数需要多一加一个左侧"()"+pre(n-1),右侧pre(n-1)+"()",包围"("+pre+")",但是需要注意的是左侧和右侧凡是遇到()()...这样的会重复,需要特殊注意,可以通过set去重,但是我没有选择,因为还需要转换,所以代码如下

public class generateParenthesis {
    public static List<String> generateParenthesis(int n) {
        List<String> l = new ArrayList<>();
        if(n==1){
            l.add("()");
            return l;
        }else if(n==2){
            l.add("(())");
            l.add("()()");
            return l;
        }else {
            List<String> temp = generateParenthesis(n-1);
            for(int i=0;i<temp.size();i++){
                l.add("("+temp.get(i)+")");
                if(i!=temp.size()-1){
                    l.add("()"+temp.get(i));
                    l.add(temp.get(i)+"()");
                }
            }
            l.add(temp.get(temp.size()-1)+"()");
        }
        return l;
    }

    public static void main(String[] args) {
        List<String> l = generateParenthesis(4);
        for(int i=0;i<l.size();i++){
            System.out.println(l.get(i));
        }
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。