Easy to understand DP solutions in Java (recursive & iterative)


  • 0
    H

    May not be the fastest code, but a different approach using DP. The idea is simple: if we know all the solutions for (n-1) as f(n-1), when adding one more parenthese, we just insert it into all possible positions of each f(n-1).

    To illustrate how to do f(n) from f(n-1), see this example: f(2) -> f(3)
    (()),()() -><from #1>: ()(()), (()()),((())), <from #2>: ()()(),(())() ()()() <- there's duplicates, that's why I use set, not list.

    The key difference, compared to several other DP/recursive solutions I saw, is that instead try to put the parentheses at the outside, rather to think how to "remove" a smallest pair (and then reverse the think to get f(n) from f(n-1).

    Note:it is easy to see that the results are mirrored, that is to say, if we have result string S, we MUST SEE s.reverse() in the same result set. Therefore, we don't have to test 2*n-1 possible positions (exclude the left and right most position), in the inner iteration, rather, just need to test i<n (recursive) and j<n (iterative).

    This is tested and accepted.

    Recursive version:

    class Solution {
        public List<String> generateParenthesis1(int n) {
            if (n <= 0) return null;
            if (n == 1) {
                List<String> ret = new ArrayList<>();
                ret.add("()");
                return ret;
            }
            
            Set<String> ret = new HashSet<>();
            List<String> temp = generateParenthesis(n - 1);
            temp.forEach(s -> {
                ret.add("()" + s);
                for (int i = 1; i < n; i++) {
                    ret.add(s.substring(0, i) + "()" + s.substring(i));
                }
                ret.add(s+"()");
                
            });
            
            return new ArrayList<>(ret);
        }
    }
    

    Iterative version:

    class Solution {
        public List<String> generateParenthesis(int n) {
            if (n <= 0) return null;
            Set<String> res = new HashSet<>();
            res.add("()");
            
            if (n == 1) return new ArrayList<>(res);
            
            for (int i = 2; i <= n; i++) {
                Set<String> temp = new Hashset<>();
                for (String s : res) {
                    temp.add("()" + s);
                    for (int j = 1; j < n; j++) {
                        temp.add(s.substring(0, j) + "()" + s.substring(j));
                    }
                    temp.add(s + "()");
                }
                res = temp;
            }
            return new ArrayList<>(res);
        }
    }
    

  • 0
    H
    This post is deleted!

Log in to reply
 

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