My Java code using DP


  • 3

    The idea is clear. Use cache to store the already calculated results, from f(0) to f(n). For each f(i), get f(j) and f(i - j - 1) from cache, 0 <= j < = j-1.

    public static List<String> generateParenthesis(int n) {
        List<List<String>> cache = new LinkedList<>();
        cache.add(Arrays.asList(""));
    
        for (int i = 1; i <= n; i++) {
            List<String> nList = new LinkedList<>();
            for (int j = 0; j < i; j++) {
                List<String> inside = cache.get(j);
                List<String> tail = cache.get(i - j - 1);
                for (int k = 0; k < inside.size(); k++) {
                    for (int l = 0; l < tail.size(); l++) {
                        nList.add("(" + inside.get(k) + ")" + tail.get(l));
                    }
                }
            }
            cache.add(nList);
        }
        return cache.get(n);
    }

  • 0
    J

    I wonder what is the time complexity for this.

    T(0) = 1
    T(1) = 1
    T(2) = T(0) * T(1)
    T(3) = T(0) * T(2) + T(1) * T(1) + T(2) * T(0)
    T(n) = 2 * (T(i) * T(n-i-1))

    So seems like if T(a) has n items and T(b) has n items, then T(a) * T(b) would take N^2. Now, T(c), let's say, has several of this operations, then T(c) would be N^3. Finally, the whole progression from T(0) to T(n) would take N^4. From the 4 nested loops, I think this is correct?


Log in to reply
 

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