JAVA, Very Easy to Follow Solution, Without String Concatenation(1ms; beats 99%)


  • 0
    C

    It is a very straightforward backtracking approach but 2 take away.

    1. With char[] as container to store the current result string, so we do not need to back deleting after we adding parentheses at a current level.
    2. Using char[] instead of string concatenation in Java will be better cause String in Java is immutable so every time you do a concatenation take O(n) time to process.
        public List<String> generateParenthesis(int n) {
            List<String> result = new ArrayList<>();
            if(n<=0)return result; 
            char[] cur = new char[2*n];
            helper(result, cur , n , n , 0);
            return result; 
        }
        
        private void helper(List<String> result , char[] cur , int lRemain, int rRemain , int index){
            if(index == cur.length){
                result.add(new String(cur));
                return; 
            }
            if(lRemain > 0){
                cur[index] = '(';
                helper(result , cur , lRemain-1, rRemain , index+1);
            }
            if(lRemain < rRemain){
                cur[index] = ')';
                helper(result, cur, lRemain , rRemain-1 , index+1);
            }
        }
    

    Any comment is welcome.


Log in to reply
 

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