Iterative DP with only 3 nested Loops


  • 0
    S

    Recursive methods have good readability, but stack can over flow if the call stack grows too big. Thus, in an interview, requiring to change a recursive approach to an iterative one is not rare.

    Another top rated iterative solution has 4 nested loops. This iterative solution is more intuitive, with less loops.

    0_1472429948186_Unknown-1.jpeg

    Look at the diagram above. Say the input n == 3. In the 2D array we store the final result at m[0][n]. The starting point m[0][0] contains an empty string. We walk from m[0][0] to m[0][n]. In each step, we can only move down or move from m[a][b] to m[a + 1][b - 1], which is the upper-right cell. When we move down, we append a "(" to the existing strings. When we move to the upper-right cell, we append a ")" to the existing strings.

    When we reach cell m[0][n], we get a valid string. There are various paths to the destination cell, figure A and B are two examples.

    Then, let's think about what strings are contained in a cell m[a][b]. As is shown in figure C, if there is a upper cell, we append "(" to all strings in the upper cell and add it to m[a][b]. If there is a cell m[a+1][b-1], which is the lower-left cell, we also append ")" to all strings in that cell and add them to m[a][b]. So, we find a way to generate new cells from existing cells. This is where we use dynamic programming.

    Figure D shows how we should loop. We traverse the diagonal lines one by one as the pink arrow indicates, from cell 1 to cell 10. Structure of the loop can be:

    for (int b = 1; b <= n; b++) {
    for (int a = b; a >= 0; a--) {
    // generate cell m[a][b-a] from cells m[a-1][b-a] and m[a+1][b-a-1]
    }
    }

    Add the code for initiating m[0][0], and finally returning m[0][n]:

    public List<String> generateParenthesis(int n) {

    	List<String>[][] matrix = new List[n + 1][n + 1];
    	matrix[0][0] = Collections.singletonList("");
    	
    	for (int b = 1; b <= n; b++) {
    		for (int a = b; a >= 0; a--) {
    			matrix[a][b - a] = new ArrayList<String>();
    			if (a != 0) {
    				// stepping down from matrix[a-1][b-a]
    				for (String s : matrix[a - 1][b - a]) {
    					matrix[a][b - a].add(s + "(");
    				}	
    			}
    			if (b != a) {
    				// stepping upper-right from matrix[a+1][b-a-1]
    				for (String s : matrix[a + 1][b - a - 1]) {
    					matrix[a][b - a].add(s + ")");
    				}
    			}
    		}
    	}
    	
    	return matrix[0][n];
    

    }

    Why it works? In short, we can append "(" to an existing string anytime, but we can only append ")" to the string if the number of '(' in the existing string is more then number of ')'. Here is an example: "(((" can be a prefix of a valid string "((()))", but "()))" can't. We can never get a valid string from "()))". By only allowing walking down or upper-right, we are forcing this rule.

    Problem 20 forced this rule with a stack, where you can only pop a stack if you previously pushed "(" into it.


  • 0
    5

    To be fair, the memory pressure grows much faster than stack depth. So recursive solution is acceptable if we can assume the maximum size of the result.

    Besides that, recursive solution produces less memory footprint than this iterative solution, since it only needs to hold the buffer and finished compositions, without the intermediate results.

    Here is a C# solution that supports my claims.

    public class Solution {
        private IList<string> results;
        
        public IList<string> GenerateParenthesis(int n) {
            results = new List<string>();
            Gen(n, n, new StringBuilder(n * 2), 0);
            return results;
        }
        
        private void Gen(int remainingOpenings, int remainingClosings, StringBuilder buffer, int unmatchedOpenings) {
            var len = buffer.Length;
            if (remainingOpenings == 0) {
                buffer.Append(')', remainingClosings);
                results.Add(buffer.ToString());
                buffer.Remove(len, remainingClosings);
            }
            else {
                buffer.Append('(');
                Gen(remainingOpenings - 1, remainingClosings, buffer, unmatchedOpenings + 1);
                buffer.Remove(len, 1);
                
                if (unmatchedOpenings > 0) {
                    buffer.Append(')');
                    Gen(remainingOpenings, remainingClosings - 1, buffer, unmatchedOpenings - 1);
                    buffer.Remove(len, 1);
                }
            }
        }
    }
    

  • 0
    Y

    Nice picture. And nice analysis from 560889223. Would anyone get more analysis on how to improve on iterative version or maybe there already is one.


Log in to reply
 

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