2
\$\begingroup\$

Given ( and ) and length of 4, generate the following combinations - ()() and (()).

Looking for code review, optimizations and best practices. Also verifying complexity to be O(2(n+1) - 1), where n is half the 'input length'.

public final class BraceCombinations {

    private BraceCombinations() {} 

    /**
     * Returns sets of valid combinations.
     *  
     * @param length    the sum of length of all- opening + closing braces
     * @return          the valid brace combinations
     */
    public static List<List<String>> getBraceCombinations(int length) {
        if (length <= 0) {
            throw new IllegalArgumentException("The length should be greater than zero");
        }

        if (length % 2 == 1) { 
            throw new IllegalArgumentException("The length should be positive");
        }

        final List<List<String>> paranthesesCombo = new ArrayList<List<String>>();
        generate(paranthesesCombo, new LinkedList<String>(), 0, 0, length/2);
        return paranthesesCombo;
    }

    private static void generate(List<List<String>> paranthesesCombo,  LinkedList<String> parenthesis, int openBrace, int closeBrace, int halfLength) {
        if (openBrace == halfLength && closeBrace == halfLength) {
            paranthesesCombo.add(new ArrayList<String>(parenthesis));
        }
        if (openBrace > halfLength || closeBrace > openBrace) {
            return;
        }
        parenthesis.add("(");
        generate(paranthesesCombo, parenthesis, openBrace + 1, closeBrace, halfLength);
        parenthesis.removeLast();

        parenthesis.add(")");
        generate(paranthesesCombo, parenthesis, openBrace, closeBrace + 1, halfLength);
        parenthesis.removeLast();
    }

    public static void main(String[] args) {
        List<List<String>> paths1 = Arrays.asList(
            Arrays.asList("(", ")")
        );
        assertEquals(paths1, getBraceCombinations(2));
        List<List<String>> paths = Arrays.asList(
                Arrays.asList("(", "(", ")", ")"),
                Arrays.asList("(", ")", "(", ")")
            );
        assertEquals(paths, getBraceCombinations(4));
    }
}
\$\endgroup\$
2
\$\begingroup\$

Jus a few minor points:

  1. I guess you have a typo here:

    if (length % 2 == 1) { 
        throw new IllegalArgumentException("The length should be positive");
    }
    

    If length is 3 it prints that The length should be positive.

  2. An exaplanatory variable would be a little bit easier to read here and it would express the purpose of the expression:

    final boolean oddLength = (length % 2 == 1);
    if (oddLength) {
        throw new IllegalArgumentException("...");
    }
    
  3. It could be easier to read and modify the expected outputs in the tests, especially if length is higher than four:

    Arrays.asList("(", "(", "(", ")", ")", ")"),
    

    I'd rather use a custom verification method here:

    private static void verifyPaths(final List<String> expectedPaths, 
            final int length) {
        final List<List<String>> braceCombinations = getBraceCombinations(length);
    
        final List<String> joinedBraceCombinations = 
            flattenBraceCombinations(braceCombinations);
    
        assertEquals(expectedPaths, joinedBraceCombinations);
    }
    
    private static List<String> flattenBraceCombinations(
            final List<List<String>> braceCombinations) {
        final Joiner joiner = Joiner.on("");
        final List<String> joinedBraceCombinations = new ArrayList<>();
        for (final List<String> braceCombination: braceCombinations) {
            final String joinedBraceCombination = joiner.join(braceCombination);
            joinedBraceCombinations.add(joinedBraceCombination);
        }
        return joinedBraceCombinations;
    }
    

    With plain strings as expected output:

    final List<String> expectedPaths = Arrays.asList(
        "((()))", 
        "(()())", 
        "(())()", 
        "()(())", 
        "()()()");
    verifyPaths(expectedPaths, 6);
    
  4. I would consider changing the current

    List<List<String>>
    

    return type to

    Set<List<String>>
    

    The order of combinations doesn't look so important and it would make the test less specified (the order of expected paths would not be important too).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.