*Java* Easy to understand recursive DP method with explanations


  • 8
    E

    For each valid parenthesis, there must be a pair whose right parenthesis is at the rightmost location. Thus, a valid parenthesis has to be of the following form:

    * ( * )
    

    where * denotes the remaining parentheses which are don't yet know (* can be empty, i.e., with 0 pair of parenthesis). However, we do know the following two important facts:

    • both two * are valid parentheses;
    • they don't overlap at all! (a pair has to be either on the left side or inside (), but cannot be the case where ( is on the left side and ) is inside ())

    If we put i parentheses inside (), there are n-i-1 to be put on the left side. This gives us a recursive formula as below:

    P(n) = P(n-i-1) x P(i)
    

    where P(n) are all valid parentheses with n parentheses.

    To this point, we are done with the algorithm, the only remaining task is coding, which is given below:

    public List<String> generateParenthesis(int n) {
    	List<String>[] lists = new LinkedList[n+1]; // store all P(k)'s for k=0,1,...,n
    	return helper(n, lists);
    }
    
    private List<String> helper(int n, List<String>[] lists) {
    	if(lists[n]!=null) return lists[n]; // if computed, reuse
    	List<String> res = new LinkedList<String>();
    	if(n<=0) {
    		lists[0] = new LinkedList<String>(Arrays.asList(""));
    		return lists[0];
    	}
    	else if(n==1) {
    		lists[1] = new LinkedList<String>(Arrays.asList("()"));
    		return lists[1];
    	}
    	// the following simply implements the recursive formula derived above
        for(int i=0; i<=n-1; i++) {
        	List<String> left = helper(n-i-1, lists);
        	List<String> inside = helper(i, lists);
        	for(String str1 : left) {
        		for(String str2 : inside) {
        			res.add(str1 + "(" + str2 + ")");
        		}
        	}
        }
        lists[n] = res; // store computed results for reuse
        return res;
    }
    

    If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java


  • 0
    C

    Elegant design!!


  • 0
    L

    dose this:"List<String>[] lists=new LinkedList<String>[n+1]" worked?


  • 0
    E

    @lovebabymao it should work, but there is a warning since List is a raw type and you are supposed to specify the data type.


  • 0
    J

    I really like ur post, thanks a lot!


Log in to reply
 

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