AC Java Solution using StringBuilder Backtracking, O(n^2) Time 3ms, O(n) Space


  • 0
    L

    Use StringBuilder for backtracking to avoid creating unused Strings.

    Since StringBuilder is a reference, we need to remove the added parentheses before other calls.

    Set initial left and right parentheses numbers as n.

    Adding left parentheses if 'left'>0, and adding right parentheses only if needing more 'right' than 'left' parentheses.

    At the end, if StringBuilder's length is equal to the n*2 value, add it to the result.

    Since it is a DFS, I suppose the time complexity is O(n^2), and using O(n) space.

    public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<String>();
            if(n<=0) return res;
            generateResult(res, n, n, n, new StringBuilder());
            return res;
        }
        
        public void generateResult (List<String> res, int max, int left, int right, StringBuilder sb) {
            if(sb.length() >= max*2) {  //check if the result is correct
                res.add(sb.toString());
                return;
            }
    
            if(left > 0) {               //add left
                    sb.append('(');
                    generateResult(res, max, left-1, right, sb);    
                    sb.deleteCharAt(sb.length()-1);     //backtracking since sb is a reference, not creating a new string
            }
                
            if(right > left){          //add right only when needing more right than left
                    sb.append(')');
                    generateResult(res, max, left, right-1, sb);    
                    sb.deleteCharAt(sb.length()-1);
            }
            
            return;
        }
    

Log in to reply
 

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