For lunch my wife made a pork and cauliflower dish. She added a few drops of Green Dragon Hot Sauce. It goes very well with pork dishes. For desert we had gypsy arm filled in with dulce de leche with strawberries on the side. Lunch was quite good. After chatting for a few and doing the dishes and pots I got back to my home office.
I decided to work on the LeetCode 22. Generate Parentheses problem. If interested please get the current description from the LeetCode web site.
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Constraints: o 1 <= n <= 8 Related Topics: o String o Backtracking
We are given a number which represents the number of pairs of parentheses ‘(‘ and ‘)’ that we should generate.
Note that this is a backtrack problem. You can read more about backtracking here.
We will solve this problem using the Java programming language and the VSCode IDE on a Windows 10 computer. This will require us to generate a test scaffold. The scaffold will read the input, call the method in questions and display the results. This code IS NOT PART OF THE SOLUTION. As a matter of fact you can skip it by solving the problem directly using the online IDE provided by LeetCode.
3 main <<< n: 3 main <<< output: [((())), (()()), (())(), ()(()), ()()()] main <<< output: [((())), (()()), (())(), ()(()), ()()()] 1 main <<< n: 1 main <<< output: [()] main <<< output: [()] 2 main <<< n: 2 main <<< output: [(()), ()()] main <<< output: [(()), ()()]
The first two test sample test cases have been provided by LeetCode. Not much to add.
class Solution {
public List<String> generateParenthesis(int n) {
}
}
The signature for the method in question is simple. We just need to receive the integer in the specified range [1:8].
/**
* Test scaffold.
* NOT PART OF THE SOLUTION
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open a buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read the number of pairs of parentheses ****
int n = Integer.parseInt(br.readLine().trim());
// **** close the buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
// **** generate and display list ****
System.out.println("main <<< output: " + generateParenthesis0(n));
// **** generate and display list ****
System.out.println("main <<< output: " + generateParenthesis1(n));
}
Our test scaffold which is NOT PART OF THE SOLUTION reads from the input line the integer that we need to pass as an argument to the method in question.
Once we display the value we call two implementations of the method in question. The returning lists are displayed.
/**
* Given n pairs of parentheses,
* generate all combinations of well-formed parentheses.
* Use backtracking.
*
* Runtime: 1 ms, faster than 72.74% of Java online submissions.
* Memory Usage: 39.5 MB, less than 15.88% of Java online submissions.
*
*/
static public List<String> generateParenthesis0(int n) {
// **** sanity check(s) ****
if (n == 1)
return Arrays.asList("()");
// **** initialization ****
ArrayList<String> al = new ArrayList<>();
// **** backtrack ****
backtrack0(al, "", 0, 0, n);
// **** return list of parenthesis ****
return al;
}
The format for backtracking calls for two methods. In the first method we can perform some sanity checks and initialize the object we will use to collect the results. The requirements call for a string list.
We are ready to call the backtrack method. After it completes execution we return the contents of the String list.
/**
* Recursive call.
*/
static private void backtrack0(List<String> al, String cs, int open, int close, int n) {
// **** base case (valid pair of parenthesis) ****
if (cs.length() == n * 2) {
al.add(cs);
return;
}
// **** decision(s) ****
if (open < n)
backtrack0(al, cs + "(", open + 1, close, n);
if (close < open)
backtrack0(al, cs + ")", open, close + 1, n);
}
The backtrack() method is recursive. We start by defining the base case. Each time we reach this condition we add the result to the string list.
We then need to specify the decisions we need to make and recursively call the backtrack() method until we are able to hit the base case. Make sure you are able to follow the logic.
Please note the number of arguments to the backtrack() method and the execution time in the comment of the method of interest.
/**
* Given n pairs of parentheses,
* generate all combinations of well-formed parentheses.
* Use backtracking.
*
* Runtime: 1 ms, faster than 72.74% of Java online submissions.
* Memory Usage: 39 MB, less than 73.93% of Java online submissions.
*/
static public List<String> generateParenthesis1(int n) {
// **** sanity check(s) ****
if (n == 1)
return Arrays.asList("()");
// **** initialization ****
List<String> al = new ArrayList<>();
// **** recursion ****
backtrack1(al, "", n, n);
// **** ****
return al;
}
This is a second attempt. The idea was to eliminate one of the arguments to the backtrack() method.
/**
* Recursive call.
*/
static private void backtrack1(List<String> al, String cs, int open, int close) {
// **** base case(s) ****
if (open < 0 || open > close)
return;
if (open == 0 && close == 0) {
al.add(cs);
return;
}
// **** recursion ****
backtrack1(al, cs + "(", open - 1, close);
backtrack1(al, cs + ")", open, close - 1);
}
After the base cases we make two recursive calls. The logic is similar with the different that we start with n and decrement down to 0. In the first case we started with 0 and incremented up to 3.
Please note the execution time in the comments section of the method of interest. Both results are quite similar. The number of test cases is limited.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John