All Balanced Parentheses in Java

The challenge

Write a function that makes a list of strings representing all of the ways you can balance n pairs of parentheses

Examples

balancedParens(0) returns ArrayList<String> with element: "" balancedParens(1) returns ArrayList<String> with element: "()" balancedParens(2) returns ArrayList<String> with elements: "()()","(())" balancedParens(3) returns ArrayList<String> with elements: "()()()","(())()","()(())","(()())","((()))"
Code language: JavaScript (javascript)

The solution in Java code

Option 1:

import java.util.ArrayList; public class BalancedParens { public static ArrayList <String> balancedParens (int n) { ArrayList<String> lst = new ArrayList<>(); StringBuilder sb = new StringBuilder(); dfs(sb,lst,0,0,n); return lst; } private static void dfs(StringBuilder sb, ArrayList<String> lst, int open, int close, int max) { if (close==max) { lst.add(sb.toString()); return; } if (open>close) { sb.append(')'); dfs(sb,lst,open,close+1,max); sb.deleteCharAt(sb.length()-1); } if (open<max) { sb.append('('); dfs(sb,lst,open+1,close,max); sb.deleteCharAt(sb.length()-1); } } }
Code language: Java (java)

Option 2:

import java.util.ArrayList; import java.util.List; public class BalancedParens { public static List<String> balancedParens (int n) { List<String> result = new ArrayList<>(n); balancedParens("", n, 0, 0, result); return result; } private static void balancedParens(String str, int n, int numOpens, int numCloses, List<String> list) { if(numCloses == n) { list.add(str); return; } if(numOpens < n) { balancedParens(str + "(", n, numOpens + 1, numCloses, list); } if(numOpens > 0 && numCloses < numOpens) { balancedParens(str + ")", n, numOpens, numCloses + 1, list); } } }
Code language: Java (java)

Option 3:

import java.util.*; public class BalancedParens { public static List<String> balancedParens(int n) { List<List<String>> sequence = new ArrayList<>(n + 1); sequence.add(Collections.singletonList("")); for (int i = 1; i <= n; i++) { List<String> currentList = new ArrayList<>(); for (int j = 0; j < i; j++) { List<String> leftList = sequence.get(j); List<String> rightList = sequence.get(i - 1 - j); for (String inner : leftList) { String braced = '(' + inner + ')'; for (String outer : rightList) currentList.add(braced + outer); } } sequence.add(currentList); } return sequence.get(n); } }
Code language: Java (java)

Test cases to validate our solution

import org.junit.Test; import static org.junit.Assert.assertEquals; import org.junit.runners.JUnit4; import java.util.*; public class SolutionTest { @Test public void testExample() { List<String> warriorsList = new ArrayList<String>(); //test for n = 0 warriorsList = BalancedParens.balancedParens(0); assertEquals(new ArrayList<String>(Arrays.asList(new String[] {""})) , warriorsList ); //test for n = 1 warriorsList = BalancedParens.balancedParens(1); assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"()"})) , warriorsList ); //test for n =2 warriorsList = BalancedParens.balancedParens(2); Collections.sort(warriorsList); assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"(())","()()"})) , warriorsList ); //test for n = 3 warriorsList = BalancedParens.balancedParens(3); Collections.sort(warriorsList); assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"((()))","(()())","(())()","()(())","()()()"})) , warriorsList ); //test for n = 4 warriorsList = BalancedParens.balancedParens(4); Collections.sort(warriorsList); assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"})) , warriorsList ); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments