Generate Parentheses

Generate Parentheses

 

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"




Naive Way:由于我已经做过一次了，现在第一反应就是那个最牛的方法，核心是通过插入新的"()"到上一级所有String每一个位置中得到所有新的这一级的String，需要一个Set去掉duplicate。

这个方法因为每个位置都插入可以防止有漏，但同时也带来大量冗余，运行时间比较慢。这道题因为输出是指数级的，算法复杂度应该也是指数级的。

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        // base case
        if(n==1){
            String s = "()";
            list.add(s);
            return list;
        }
        // recursive
        List<String> preLevel = generateParenthesis(n-1);
        Set<String> set = new HashSet<String>();
        for(int i = 0;i < preLevel.size();i++){
            String orig = preLevel.get(i);
            for(int j = 0;j <= orig.length();j++){
                String s = orig.substring(0,j)+"()"+orig.substring(j,orig.length());
                if(!set.contains(s))
                    set.add(s);
            }
        }
        list.addAll(set);
        return list;
    }
}
 

然后我第一次做是用DP做的。需要存贮每一级的String，空间复杂度极高。基本思路就是
7 = 1+6
7 = 2+5
7 = 3+4
7 = 4+3
...
再加上一个
7 = "("+6+")"

public class Solution {
        public List<String> generateParenthesis(int n) {
            List<List<String>> opt = new ArrayList<List<String>>();
            // base case
            List<String> zero = new ArrayList<String>();
            List<String> one = new ArrayList<String>();
            one.add("()");
            opt.add(zero);
            opt.add(one);
            // iteration
            for(int i = 2;i <= n;i++){
                List<String> current = new ArrayList<String>();
                HashSet<String> visited = new HashSet<String>();
                for(int j = 1;j <= i/2;j++){
                    List<String> lst = combine(opt.get(j), opt.get(i-j), visited);
                    for(int u = 0;u < lst.size();u++)
                        current.add(lst.get(u));
                }
                for(int j = 0;j < opt.get(i-1).size();j++){
                    String outer = "("+opt.get(i-1).get(j)+")";
                    current.add(outer);
                }
                opt.add(current);
            }
           
            return opt.get(n);
        }
       
        private List<String> combine(List<String> a, List<String> b, HashSet<String> visited){
            List<String> output = new ArrayList<String>();
            for(int i = 0;i < a.size();i++){
                for(int j = 0;j < b.size();j++){
                    String left = a.get(i) + b.get(j);
                    String right = b.get(j) + a.get(i);
                    if(!visited.contains(left)){
                        visited.add(left);
                        output.add(left);
                    }
                    if(!visited.contains(right)){
                        visited.add(right);
                        output.add(right);
                    }
                }
            }
            return output;
        }
}


Improved Way:这是我当时看到的最牛的做法，现在已经找不到那个提问了，还好把代码记了下来，是用DFS做的。核心思想就是从一个"("出发，可以从左边加新的"("，也可以从右边加新的")"，而这相当于它的两个子节点。然后对这样的一棵树进行DFS。


class Node{
       
        String str; // "(" , ")"s
        int used; // # of "("s used
        int left; // # of "("s need to be matched
        Node(String c,int x, int y){
            str = new String(c);
            used = x;
            left = y;
        }
    }

public List<String> generateParenthesis(int n) {
            List<String> output = new ArrayList<String>();
            Stack<Node> stack = new Stack<Node>();
            Node initial = new Node("(",1,1);
            stack.push(initial);
            while(!stack.isEmpty()){
                Node node = stack.pop();
                // check valid
                if(node.used == n && node.left == 0){
                    output.add(node.str);
                }
               
                // push in next possible Node
                if(node.used < n){
                    Node leftParenNode = new Node(node.str+"(",node.used+1,node.left+1);
                    stack.push(leftParenNode);
                }
                if(node.left > 0){
                    Node rightParenNode = new Node(node.str+")",node.used,node.left-1);
                    stack.push(rightParenNode);
                }
            }
           
            return output;
        }