Summary: Java DP & Recursive methods


  • 1
    1. Recursive method ( which I believe is more straightforward):
    public class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>(); 
            if (n == 0) {
                res.add("");
                return res; 
            } 
            if (n == 1) {
                res.add("()");
                return res; 
            }
            
            for (int i = 0; i <= n-1; i++) {
                String cur = "";
                List<String> a = generateParenthesis(i);
                List<String> b = generateParenthesis(n-i-1);
                for (String str1:a) {
                    for (String str2:b) {
                           res.add(str1 + "(" + str2 + ")"); 
                    }
                }
            }
            return res; 
        }
    
    1. DP method:
    public class Solution {
        public List<String> generateParenthesis(int n) {
            List<List<String>> lists = new ArrayList<>();
            List<String> zero = new ArrayList<>(); 
            zero.add("");
            lists.add(zero);
            //f(n) = "("f(0)")"f(n-1) , "("f(1)")"f(n-2) "("f(2)")"f(n-3) ... "("f(i)")"f(n-1-i) ... "(f(n-1)")"
            for (int i = 1; i <= n ; i++) {
                List<String> list = new ArrayList<>(); 
                for (int j = 0; j <= i-1; j++) {
                    for (String first:lists.get(j)) { 
                        for (String second:lists.get(i-j-1)) { 
                            list.add("(" + first + ")" + second);
                            //or list.add(first + "(" + second + ")");
                        }
                    }
                }
                lists.add(list);
            }
            return lists.get(n);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.