Java fast 2ms backtracking Solution beats 90.15% of submissions


  • 0
    M

    Following solution exploits the fact that appending strings to Java StringBuilder is extremely fast as compared to simply concatenating strings together

    public class Solution {
        public List<String> generateParenthesis(int n) {
            if (n==0) {return new ArrayList();}
            List<String> list = new ArrayList();
            StringBuilder sb = new StringBuilder();
            generateParan(list, n, n, sb);
            return list;
        }
        
        private void generateParan(List<String> list, int openParan, int closeParan, StringBuilder sb) {
            if (openParan ==0 && closeParan==0) {
                list.add(sb.toString());
                return;
            } else if (closeParan<openParan) {return;}
            if (openParan>0) {
                sb.append("(");
                generateParan(list, openParan-1, closeParan, sb);
                sb.deleteCharAt(sb.length()-1);
            }
            if (closeParan>0) {
                sb.append(")");
                generateParan(list, openParan, closeParan-1, sb);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
    

Log in to reply
 

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