2ms Java solution with explanation and sane variable names


  • 0
    B

    Explanation:

    Every string must begin with an open parenthesis, which is why our initial call to generate uses nOpenUsed = 1, nClosedUsed = 0, and the StringBuilder sb is constructed with "(".

    Given a valid partially-built string:

    • If the string has used all available open and closed parentheses, then the string is actually complete and we add it to the output list;
    • Otherwise,
      • We can add a close parenthesis at the end whenever we have used fewer close parentheses than open parentheses so far.
      • We can add an open parenthesis at the end so long as we haven't used all of them already.

    Code:

    public List<String> generateParenthesis(int n) {
         List<String> outputList = new ArrayList<>();
         generate(n, 1, 0, new StringBuilder("("), outputList);
         return outputList;
     }
    
     private void generate(int numPairs, int nOpenUsed, int nClosedUsed, StringBuilder sb, List<String> outputList) {
         if (nOpenUsed == numPairs && nClosedUsed == numPairs) {
             outputList.add(sb.toString());
             return;
         }
    
         if (nOpenUsed > nClosedUsed) {
             StringBuilder sb2 = (nOpenUsed < numPairs) ? new StringBuilder(sb) : sb;
             sb2.append(')');
             generate(numPairs, nOpenUsed, nClosedUsed + 1, sb2, outputList);
         }
         if (nOpenUsed < numPairs) {
             sb.append('(');
             generate(numPairs, nOpenUsed + 1, nClosedUsed, sb, outputList);
         }
     }

Log in to reply
 

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