Fast concise Java solution using char[] instead of String or StringBuilder (beats 92%)


  • 1
    B

    This solution is very close to other solutions: just count how many parentheses do we need to open, and how much to close. If we can open open, if we can close, close, and modify the counters accordingly. The trick is that, we dok now how long our string will be, so we can allocate a char array beforehand, and use that to construct our strings when we know that it is full.

    public class Solution {
        
        private void buildResult(List<String> result, char[] chars, int i, int toOpen, int toClose) {
            if(i == chars.length) {
                result.add(new String(chars));
                return;
            }
            
            if(toOpen > 0) {
                chars[i] = '(';
                buildResult(result, chars, i + 1, toOpen - 1, toClose + 1);
            }
            if(toClose > 0) {
                chars[i] = ')';
                buildResult(result, chars, i + 1, toOpen, toClose - 1);
            }
        }
        
        public List<String> generateParenthesis(int n) {
            if(n < 0) {
                return Collections.emptyList();
            }
            if(n == 0) {
                return Collections.singletonList("");
            }
            
            char[] chars = new char[n * 2];
            List<String> result = new LinkedList<>();
            buildResult(result, chars, 0, n, 0);
            return result;
        }
    }

Log in to reply
 

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